WEKO3
アイテム
Graph Orientations Optimizing the Number of Light or Heavy Vertices
http://hdl.handle.net/10228/0002000096
http://hdl.handle.net/10228/0002000096944eb789-d796-4411-8760-929c1706e007
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
AsahiroJanssonMiyanoOno2015.19.1.pdf (351 KB)
|
|
| Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-09-13 | |||||||||||||||||||
| 資源タイプ | ||||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||||
| タイトル | ||||||||||||||||||||
| タイトル | Graph Orientations Optimizing the Number of Light or Heavy Vertices | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| 言語 | ||||||||||||||||||||
| 言語 | eng | |||||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× Jansson, Jesper
× 宮野, 英次
WEKO
6037
× Ono, Hirotaka
|
|||||||||||||||||||
| 抄録 | ||||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||||
| 内容記述 | This paper introduces four graph orientation problems named MAXIMIZE W-LIGHT, MINIMIZE W-LIGHT, MAXIMIZE W-HEAVY, and MINIMIZE W-HEAVY, where W can be any fixed non-negative integer. In each problem, the input is an undirected, unweighted graph G and the objective is to assign a direction to every edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. A number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs are derived. In particular, it is shown that MAXIMIZE 0-LIGHT and MINIMIZE 1-HEAVY are identical to MAXIMUM INDEPENDENT SET and MINIMUM VERTEX COVER, respectively, so by allowing the value of W to vary, we obtain a new generalization of the two latter problems. © Journal of Graph Algorithms and Applications. | |||||||||||||||||||
| 言語 | en | |||||||||||||||||||
| 書誌情報 |
en : Journal of Graph Algorithms and Applications 巻 19, 号 1, p. 441-465, 発行日 2015-01-01 |
|||||||||||||||||||
| 出版社 | ||||||||||||||||||||
| 出版者 | Brown University | |||||||||||||||||||
| DOI | ||||||||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||||
| 関連識別子 | https://doi.org/10.7155/jgaa.00371 | |||||||||||||||||||
| ISSN | ||||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||||
| 収録物識別子 | 1526-1719 | |||||||||||||||||||
| 出版タイプ | ||||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||||
| 査読の有無 | ||||||||||||||||||||
| 値 | yes | |||||||||||||||||||
| 研究者情報 | ||||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||||
