ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング


インデックスリンク

インデックスツリー

  • RootNode

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究報告
  2. アルゴリズム(AL)
  3. 2016
  4. 2016-AL-158

距離限定部分グラフ探索問題に対する近似アルゴリズム

https://ipsj.ixsq.nii.ac.jp/records/164043
https://ipsj.ixsq.nii.ac.jp/records/164043
3aac5669-e343-4dc5-a8ad-719b7aef8838
名前 / ファイル ライセンス アクション
IPSJ-AL16158018.pdf IPSJ-AL16158018.pdf (436.8 kB)
Copyright (c) 2016 by the Information Processing Society of Japan
オープンアクセス
Item type SIG Technical Reports(1)
公開日 2016-06-17
タイトル
タイトル 距離限定部分グラフ探索問題に対する近似アルゴリズム
タイトル
言語 en
タイトル Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
言語
言語 jpn
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_18gh
資源タイプ technical report
著者所属
九州産業大学情報科学部
著者所属
九州工業大学大学院情報工学研究院システム創成情報工学研究系
著者所属
九州工業大学大学院情報工学研究院システム創成情報工学研究系
著者所属
九州工業大学大学院情報工学研究院システム創成情報工学研究系
著者名 朝廣, 雄一

× 朝廣, 雄一

朝廣, 雄一

Search repository
土井, 悠也

× 土井, 悠也

土井, 悠也

Search repository
志水, 宏宇

× 志水, 宏宇

志水, 宏宇

Search repository
宮野, 英次

× 宮野, 英次

宮野, 英次

Search repository
著者名(英) Yuichi, Asahiro

× Yuichi, Asahiro

en Yuichi, Asahiro

Search repository
Yuya, Doi

× Yuya, Doi

en Yuya, Doi

Search repository
Hirotaka, Shimizu

× Hirotaka, Shimizu

en Hirotaka, Shimizu

Search repository
Eiji, Miyano

× Eiji, Miyano

en Eiji, Miyano

Search repository
論文抄録
内容記述タイプ Other
内容記述 グラフ G=(V,E) 中の頂点集合 S ⊆ V を考える.S 中の任意の頂点 u, v の組に対して,G 中での u と v の間の距離が高々 d である場合に S は d-クリークであると言う.また,S により誘導される G の部分グラフの直径が高々 d の場合には,S は d-クラブであると言う.与えられた n 頂点グラフに対して,Max d-Clique 問題 (または Max d-Club 問題) の目的は,G 中の最大 d-クリーク (または最大 d-クラブ) を発見することである.任意の ε>0 に対して,Max 1-Clique と Max 1-Club は,P = NP でない限り多項式時間で n1-ε- 近似できない.なぜならば,これらの問題は Max Clique と同じ問題であり,Max Clique が P = NP でない限り多項式時間で n1-ε- 近似できないからである ([5], [10]).さらに,任意の固定された d ≧ 2 と任意の ε > 0 に対して,Max d-Club は P = NP でない限り n1/2-ε- 近似できないことも知られている [2].Max d-Club の近似上界に関しては,任意の偶数 d ≧ 2 に対する多項式時間 O(n1/2)- 近似アルゴリズムが著者らのグループにより提案されている [2].しかしながら,奇数 d ≧ 3 に対しては,このアルゴリズムの近似率は O(n2/3) に悪化するため,近似下界 Ω(n1/2-ε) との乖離が依然として残っている [2].本稿ではまず,Max d-Club の近似上界の改善を行う.すなわち,任意の奇数 d ≧ 3 に対して多項式時間 O(n1/2)- 近似アルゴリズムを提案する.そして同様のアイデアを用いて,任意の d ≧ 2 に対して Max d-Clique も多項式時間で O(n1/2)- 近似できることを示す.それとともに P = NP でない限り,任意の ε > 0 に対して,Max d-Clique も n1/2-ε- 近似できないことについて述べる.
論文抄録(英)
内容記述タイプ Other
内容記述 A d-clique in a graph G = (V,E) is a subset S ⊆ V of vertices such that for pairs of vertices u, v ∈ S, the distance between u and v is at most d in G. A d-club in a graph G = (V,E) is a subset S0 ⊆ V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Max d-Clique (Max d-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1-ε for any ε > 0 unless P = NP since they are identical to Max Clique [5], [10]. Also, it is known [2] that it is NP-hard to approximate Max d-Club to within a factor of n1/2-ε for any fixed d ≧ 2 and for any ε > 0. As for approximability of Max d-Club, there exists a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for any even d ≧ 2 [2]. For any odd d ≧ 3, however, there still remains a gap between the O(n2/3)-approximability and the Ω(n1/2-ε)-inapproximability for Max d-Club [2]. In this paper, we first strengthen the approximability result for Max d-Club; we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for Max d-Club for any odd d ≧ 3. Then, by using the similar ideas, we show the O(n1/2)-approximation algorithm for Max d-Clique for any d ≧ 2. This is the best possible in polynomial time unless P = NP, as we can prove the Ω(n1/2-ε)-inapproximability.
書誌レコードID
収録物識別子タイプ NCID
収録物識別子 AN1009593X
書誌情報 研究報告アルゴリズム(AL)

巻 2016-AL-158, 号 18, p. 1-6, 発行日 2016-06-17
ISSN
収録物識別子タイプ ISSN
収録物識別子 2188-8566
Notice
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
出版者
言語 ja
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-20 11:03:09.784326
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3