| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-08-10 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Graph Orientation Algorithms to Minimize the Maximum Outdegree |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
宮野, 英次
Ono, Hirotaka
Zenmyo, Kouhei
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
We study the problem of orienting the edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be NP-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, or more generally, a graph with identically weighted edges, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, min{wmax/wmin ; (2-ε)}-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and " is some small positive real number that depends on the input. |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Twelfth Computing: The Australasian Theory Symposium (CATS2006), 16-19 January, 2006, Hobart, Australia |
| 書誌情報 |
Conferences in Research and Practice in Information Technology Series
巻 51,
発行日 2006
|
| 出版社 |
|
|
出版者 |
Australian Computer Society Inc. |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-192068233-0 |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10347756.pdf (180 KB)
