WEKO3
アイテム
Complexity of finding maximum regular induced subgraphs with prescribed degree
http://hdl.handle.net/10228/0002000092
http://hdl.handle.net/10228/00020000921a8da788-6bf7-4d13-874f-abd524363e71
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10347749.pdf (417 KB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-09-12 | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | Complexity of finding maximum regular induced subgraphs with prescribed degree | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| その他のタイトル | ||||||||||||||||||
| その他のタイトル | Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× Eto, Hiroshi× Ito, Takehiro
× 宮野, 英次
WEKO
6037
|
|||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
en : Theoretical Computer Science 巻 550, p. 21-35, 発行日 2014-07-17 |
|||||||||||||||||
| 出版社 | ||||||||||||||||||
| 出版者 | Elsevier | |||||||||||||||||
| DOI | ||||||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.tcs.2014.07.008 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 0304-3975 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||
| 収録物識別子 | 1879-2294 | |||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||
| 権利情報 | Copyright (c) 2014 Elsevier B.V. All rights reserved. | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Bipartite graph | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Chordal graph | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Graph algorithm | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Inapproximability | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Planar graph | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Regular induced subgraph | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Treewidth | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||
| 査読の有無 | ||||||||||||||||||
| 値 | yes | |||||||||||||||||
| 研究者情報 | ||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||
