WEKO3
アイテム
Distance-d independent set problems for bipartite and chordal graphs
http://hdl.handle.net/10228/00008984
http://hdl.handle.net/10228/00008984573bacba-6fdb-4861-852a-0ae39781f3f4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10347752.pdf (161.3 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-10-03 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Distance-d independent set problems for bipartite and chordal graphs | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
Eto, Hiroshi
× Eto, Hiroshi× Guo, Fengrui× 宮野, 英次
WEKO
6037
|
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | The paper studies a generalization of the INDEPENDENT SET problem (IS for short). A distance-d independent set for an integer d≥2 in an unweighted graph G=(V,E) is a subset S⊆V of vertices such that for any pair of vertices u,v∈S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the DISTANCE-d INDEPENDENT SET problem (D d IS for short) is to decide whether G contains a distance-d independent set S such that |S|≥k. D2IS is identical to the original IS. Thus D2IS is NP-complete even for planar graphs, but it is in P for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance-d independent set: (1) We first prove that for any ε>0 and any fixed integer d≥3, it is NP-hard to approximate MaxD d IS to within a factor of n1/2−ε for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is W[1]-hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP-complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP-complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1]-hardness of ParaD d IS(k) on chordal graphs for any odd d≥3. | |||||||||||||
| 書誌情報 |
Journal of Combinatorial Optimization 巻 27, p. 88-99, 発行日 2013-01-10 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Springer | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1007/s10878-012-9594-4 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 1573-2886 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 1382-6905 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) Springer Science+Business Media New York 2013. This is a post-peer-review, pre-copyedit version of an article published in Journal of Combinatorial Optimization. The final authenticated version is available online at: https://doi.org/10.1007/s10878-012-9594-4. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Distance-d independent set | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Bipartite graphs | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Chordal graphs | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Computational complexity | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10347752 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 10664 | |||||||||||||
