Inapproximability of maximum r-regular induced connected subgraph problems

DOI 機関リポジトリ 機関リポジトリ (HANDLE) Web Site 被引用文献1件 参考文献23件 オープンアクセス
  • ASAHIRO Yuichi
    Department of Information Science, Kyushu Sangyo University
  • ETO Hiroshi
    Department of System Design and Informatics, Kyushu Institute of Technology
  • MIYANO Eiji
    Department of System Design and Informatics, Kyushu Institute of Technology

書誌事項

タイトル別名
  • Inapproximability of Maximum <i>r</i>-Regular Induced Connected Subgraph Problems
公開日
2013
資源種別
journal article
DOI
  • 10.1587/transinf.e96.d.443
公開者
一般社団法人 電子情報通信学会

この論文をさがす

説明

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.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (23)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

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

問題の指摘

ページトップへ