文献
J-GLOBAL ID:202002279579130523   整理番号:20A0054004

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

Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
著者 (4件):
資料名:
巻: 119  号: 249(COMP2019 18-28)(Web)  ページ: 11-18 (WEB ONLY)  発行年: 2019年10月18日 
JST資料番号: S0532B  ISSN: 0913-5685  資料種別: 会議録 (C)
記事区分: 原著論文  発行国: 日本 (JPN)  言語: 日本語 (JA)
抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本論文では独立点集合列挙問題について取り組む.極大な独立点集合列挙問題に対しては効率良い非自明なアルゴリズムが多く開発されている一方で,非極大な場合の列挙問題に対しては自明なアルゴリズムより良いアルゴリズムや良い解析が行われていない.そこで,我々は独立点集合列挙アルゴリズムEISがならしO(q)時間,線形空間で動作することを示した.ここで,qは入力グラフ中の最大クリークサイズである.また,qの厳密に計算することはNP-困難であることが知られているが,EISはqの具体的な値を知らなくても正しく動作する.EISは単純なアルゴリズムであるにも関わらず,このアルゴリズムは平面グラフ,二部グラフ,そして,定数縮退グラフといった最大クリークサイズが定数であるグラフに対して最適なアルゴリズムである.(著者抄録)
シソーラス用語:
シソーラス用語/準シソーラス用語
文献のテーマを表すキーワードです。
部分表示の続きはJDreamⅢ(有料)でご覧いただけます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。

準シソーラス用語:
シソーラス用語/準シソーラス用語
文献のテーマを表すキーワードです。
部分表示の続きはJDreamⅢ(有料)でご覧いただけます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。

分類 (1件):
分類
JSTが定めた文献の分類名称とコードです
計算理論 
引用文献 (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件):
タイトルに関連する用語
J-GLOBALで独自に切り出した文献タイトルの用語をもとにしたキーワードです

前のページに戻る