WEKO3
アイテム
Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems
http://hdl.handle.net/10228/0002000071
http://hdl.handle.net/10228/00020000719afa2859-2843-411b-ac55-987f2e3dca18
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
E96.D_443.pdf (444 KB)
|
|
| Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-08-22 | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| その他のタイトル | ||||||||||||||||||
| その他のタイトル | Inapproximability of Maximum <i>r</i>-Regular Induced Connected Subgraph Problems | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× Eto, Hiroshi
× 宮野, 英次
WEKO
6037
|
|||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | Given a connected graph G = (V,E) on n vertices, the Maximum r-Regular Induced Connected Subgraph (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P = NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P = NP. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
en : IEICE Transactions on Information and Systems 巻 E96.D, 号 3, p. 443-449, 発行日 2013-03-01 |
|||||||||||||||||
| 出版社 | ||||||||||||||||||
| 出版者 | 電子情報通信学会 | |||||||||||||||||
| DOI | ||||||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||
| 関連識別子 | https://doi.org/10.1587/transinf.E96.D.443 | |||||||||||||||||
| CRID | ||||||||||||||||||
| 識別子タイプ | URI | |||||||||||||||||
| 関連識別子 | https://cir.nii.ac.jp/crid/1390282679356399488 | |||||||||||||||||
| NCID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AA10826272 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 0916-8532 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||
| 収録物識別子 | 1745-1361 | |||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||
| 権利情報 | Copyright (c) 2013 The Institute of Electronics, Information and Communication Engineers | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | induced connected subgraph | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | regularity | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | NP-hardness | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | inapproximability | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||
| 査読の有無 | ||||||||||||||||||
| 値 | yes | |||||||||||||||||
| 研究者情報 | ||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||
