文献

J-GLOBAL ID：201702226199557060   整理番号：17A0544985

グラフ中に含まれる縮退部分グラフの列挙

著者 (2件)： 和佐州洋 (国立情報学研) ,  宇野毅明 (国立情報学研)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2017  号： AL-161  ページ： Vol.2017-AL-161,No.5,1-7 (WEB ONLY)  発行年： 2017年01月10日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,グラフに含まれ,かつ,与えられた縮退数を持つ部分グラフを列挙する問題について考察する。あるグラフGの縮退数がkであるとは,Gの任意の誘導グラフが高々kの次数を持つ頂点を含むときをいう。主結果として,与えられたグラフGと,正整数kに対して,多項式時間の前処理の後,(1)Gに含まれるk-縮退誘導グラフを解1つあたりO(Δ(k+log n))時間で,(2)Gに含まれるk-縮退部分グラフを解1つあたりO(log n)時間で,列挙するアルゴリズムを与えた。ただし,nをG中の頂点数とし,ΔをG中の最大次数とする。また,ともに使用する空間計算量は入力グラフのサイズに線形である。これらは逆探索法[Avis and Fukuda,DAM,1996]に基づいたアルゴリズムであり,縮退部分グラフを列挙するアルゴリズムとしては,初の多項式遅延のアルゴリズムである。(著者抄録)

シソーラス用語： *部分グラフ ,  無次元数 ,  *頂点 ,  *計算理論 ,  *アルゴリズム ,  計算量 ,  探索問題 ,  無向グラフ ,  部分集合 ,  定理 ,  次数
準シソーラス用語： 縮退部分グラフ ,  多項式時間 ,  グラフ列挙アルゴリズム ,  逆探索法 ,  縮退誘導グラフ

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (20件)：

• Avis, D. and Fukuda, K.: Reverse search for enumeration, Discrete Applied Mathematics, Vol. 65, No. 1-3, pp. 21-46 (1996).
• Basavaraju, M., Heggernes, P., van t Hof, P., Saei, R. and Villanger, Y.: Maximal Induced Matchings in TriangleFree Graphs, WG 2014: the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 8747, Springer International Publishing, pp. 93-104 (online), DOI: 10.1007/978-3-319-12340-0 8 (2014).
• Bauer, R., Krug, M. and Wagner, D.: Enumerating and Generating Labeled k-degenerate Graphs, ANALCO 2010: the 7th Workshop on Analytic Algorithmics and Combinatorics, Society for Industrial and Applied Mathematics, pp. 90-98 (online), DOI: 10.1137/1.9781611973006.12 (2010).
• Birmel?, E., Ferreira, R., Grossi, R., Marino, A., Pisanti, N., Rizzi, R. and Sacomoto, G.: Optimal Listing of Cycles and st-Paths in Undirected Graphs, In proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), New Orleans, LA, USA, pp. 1884-1896 (online), DOI: 10.1137/1.9781611973105.134 (2012).
• Conte, A., Grossi, R., Marino, A. and Versari, L.: Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 55, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 148:1-148:15 (online), DOI: 10.4230/LIPIcs.ICALP.2016.148 (2016).

タイトルに関連する用語 (3件)： グラフ ,  縮退 ,  部分グラフ