WEKO3
アイテム
Graph Orientation to Maximize the Minimum Weighted Outdegree
http://hdl.handle.net/10228/0002000128
http://hdl.handle.net/10228/0002000128b7aed9d3-f417-4fe9-9d62-820677de1fc2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10347757.pdf (331 KB)
|
|
| Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-10-02 | |||||||||||||||||||
| 資源タイプ | ||||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||||
| タイトル | ||||||||||||||||||||
| タイトル | Graph Orientation to Maximize the Minimum Weighted Outdegree | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| その他のタイトル | ||||||||||||||||||||
| その他のタイトル | GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| 言語 | ||||||||||||||||||||
| 言語 | eng | |||||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× Jansson, Jesper
× 宮野, 英次
WEKO
6037
× Ono, Hirotaka
|
|||||||||||||||||||
| 抄録 | ||||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||||
| 内容記述 | We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 – ε for any constant ε > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmaz/wmin-approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph. | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| 書誌情報 |
en : International Journal of Foundations of Computer Science 巻 22, 号 03, p. 583-601, 発行日 2011 |
|||||||||||||||||||
| 出版社 | ||||||||||||||||||||
| 出版者 | World Scientific Publishing | |||||||||||||||||||
| DOI | ||||||||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||||
| 関連識別子 | https://doi.org/10.1142/S0129054111008246 | |||||||||||||||||||
| ISSN | ||||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||||
| 収録物識別子 | 0129-0541 | |||||||||||||||||||
| ISSN | ||||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||||
| 収録物識別子 | 1793-6373 | |||||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||||
| 権利情報 | Electronic version of an article published as International Journal of Foundations of Computer Science, VOL. 22, NO. 03 https://doi.org/10.1142/S0129054111008246 © copyright World Scientific Publishing Company, https://www.worldscientific.com/worldscinet/ijfcs. | |||||||||||||||||||
| キーワード | ||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||
| 主題 | Graph orientation | |||||||||||||||||||
| キーワード | ||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||
| 主題 | Approximation algorithm | |||||||||||||||||||
| キーワード | ||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||
| 主題 | Hardness of approximation | |||||||||||||||||||
| キーワード | ||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||
| 主題 | Scheduling | |||||||||||||||||||
| キーワード | ||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||
| 主題 | Maximum flow | |||||||||||||||||||
| 出版タイプ | ||||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||||
| 査読の有無 | ||||||||||||||||||||
| 値 | yes | |||||||||||||||||||
| 研究者情報 | ||||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||||
