WEKO3
アイテム
Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
http://hdl.handle.net/10228/0002000093
http://hdl.handle.net/10228/00020000938abbf2df-2225-4271-893d-08f8cb6705ed
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10347755.pdf (265 KB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-09-12 | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| その他のタイトル | ||||||||||||||||||
| その他のタイトル | Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× 宮野, 英次
WEKO
6037
× Ono, Hirotaka
|
|||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in p for trees, weak np-hard for planar bipartite graphs, and strong np-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in p for cactus graphs, (ii) weakly np-hard for outerplanar graphs, and also (iii) strongly np-hard for graphs which are both planar and bipartite. This implies the np-hardness for P4-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the np-hardness for series–parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
en : Discrete Applied Mathematics 巻 159, 号 7, p. 498-508, 発行日 2010-12-31 |
|||||||||||||||||
| 出版社 | ||||||||||||||||||
| 出版者 | Elsevier | |||||||||||||||||
| DOI | ||||||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.dam.2010.11.003 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 0166-218X | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||
| 収録物識別子 | 1872-6771 | |||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||
| 権利情報 | Copyright (c) 2010 Elsevier B.V. All rights reserved. | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Graph orientation | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Min–max optimization | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | np-hardness | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Cactus | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | (Outer)planar | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | (P4-)bipartite | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Series–parallel | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||
| 査読の有無 | ||||||||||||||||||
| 値 | yes | |||||||||||||||||
| 研究者情報 | ||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||
