文献

J-GLOBAL ID：202002279579130523   整理番号：20A0054004

最大クリークサイズが定数であるグラフに対する独立点集合のならし定数時間列挙

Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number

著者 (4件)： 栗田和宏 (北大 大学院情報科学研究科) ,  和佐州洋 (国立情報学研) ,  宇野毅明 (国立情報学研) ,  有村博紀 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 119  号： 249(COMP2019 18-28)(Web)  ページ： 11-18 (WEB ONLY)  発行年： 2019年10月18日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では独立点集合列挙問題について取り組む.極大な独立点集合列挙問題に対しては効率良い非自明なアルゴリズムが多く開発されている一方で,非極大な場合の列挙問題に対しては自明なアルゴリズムより良いアルゴリズムや良い解析が行われていない.そこで,我々は独立点集合列挙アルゴリズムEISがならしO(q)時間,線形空間で動作することを示した.ここで,qは入力グラフ中の最大クリークサイズである.また,qの厳密に計算することはNP-困難であることが知られているが,EISはqの具体的な値を知らなくても正しく動作する.EISは単純なアルゴリズムであるにも関わらず,このアルゴリズムは平面グラフ,二部グラフ,そして,定数縮退グラフといった最大クリークサイズが定数であるグラフに対して最適なアルゴリズムである.(著者抄録)

シソーラス用語： *クリーク ,  *グラフ理論 ,  NP困難 ,  平面グラフ ,  部分グラフ ,  *アルゴリズム ,  計算量 ,  解析 ,  計算量解析 ,  最大クリーク
準シソーラス用語： NP困難問題 ,  二部グラフ ,  列挙問題

分類 (1件)： 計算理論  (JB02000A)

引用文献 (19件)：

• D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Appl. Math., 65(1):21-46, 1996.
• M. Bonamy, O. Defrain, M. Heinrich, and J.-F. Raymond. Enumerating Minimal Dominating Sets in Triangle-Free Graphs. In Proc. STACS 2019, volume 126 of LIPIcs, pages 16:1-16:12, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
• S. Cohen, B. Kimelfeld, and Y. Sagiv. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. J. Comput. Syst. Sci., 74(7):1147 - 1159, 2008.
• A. Conte, R. Grossi, A. Marino, T. Uno, and L. Versari. Listing maximal independent sets with minimal space and bounded delay. In Proc. SPIRE 2017, volume 10508, pages 144-160. Springer, 2017.
• A. Conte, R. Grossi, A. Marino, and L. Versari. Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques. In Proc. ICALP 2016, volume 55 of LIPIcs, pages 148:1-148:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.

タイトルに関連する用語 (5件)： 最大クリーク ,  サイズ ,  定数 ,  グラフ ,  点集合