| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2024-01-09 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Eto, Hiroshi
Ito, Takehiro
Liu, Zhilong
宮野, 英次
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d≥2, a distance-d independent set of an unweighted graph G=(V, E) is a subset S⊆V of vertices such that for any pair of vertices u, v∈S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r≥3) and planar graphs, as follows: (1) For every fixed integers d≥3 and r≥3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-2/d)-approximation algorithms when restricted to d=r=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs. |
|
言語 |
en |
| 書誌情報 |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
巻 E105.A,
号 9,
p. 1211-1222,
発行日 2022-09-01
|
| 出版社 |
|
|
出版者 |
電子情報通信学会 |
|
言語 |
ja |
| DOI |
|
|
関連タイプ |
isIdenticalTo |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1587/transfun.2021DMP0017 |
| CRID |
|
|
関連タイプ |
isIdenticalTo |
|
|
識別子タイプ |
URI |
|
|
関連識別子 |
https://cir.nii.ac.jp/crid/1390293268648730496 |
| NCID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA10826239 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1745-1337 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0916-8508 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2022 The Institute of Electronics, Information and Communication Engineers |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
distance independent set problem |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
regular graphs |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
planar graphs |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
(in)approximability |
| 出版タイプ |
|
|
出版タイプ |
VoR |
|
出版タイプResource |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
e105-a_9_1211.pdf (2.2 MB)
