Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

DOI DOI 機関リポジトリ 機関リポジトリ 機関リポジトリ (HANDLE) ほか3件をすべて表示 一部だけ表示 被引用文献2件 参考文献21件

書誌事項

公開日
2022-09-01
資源種別
journal article
DOI
  • 10.1587/transfun.2021dmp0017
  • 10.1007/978-3-319-48749-6_20
公開者
一般社団法人 電子情報通信学会

この論文をさがす

説明

<p>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.</p>

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (21)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ