文献

J-GLOBAL ID：202402280132034678   整理番号：24A0421448

弦グラフの部分クラスにおける極大誘導部分グラフ列挙への多項式遅延アルゴリズム

著者 (4件)： 佐藤嶺 (北大) ,  小林靖明 (北大) ,  栗田和宏 (名古屋大) ,  和佐州洋 (法政大)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 123  号： 325(COMP2023 16-27)  ページ： 29-36 (WEB ONLY)  発行年： 2023年12月15日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフの遺伝的性質Pについて,与えられたグラフの中の性質Pを満たす極大な誘導部分グラフを列挙する問題(極大誘導P部分グラフ列挙問題)は,様々な性質Pに関してよく研究されており,特に多項式遅延列挙可能性については非常に活発に議論されているトピックである.本研究では,Pが弦グラフの部分クラスの場合に着目する.具体的には,Pが自明な理想グラフ(trivially perfect graph)やブロックグラフであるときに,極大誘導P部分グラフ列挙問題を解く多項式遅延アルゴリズムを与える.この結果は,Cao(ESA2023)のアルゴリズムの単純化や多項式遅延列挙可能性の観点で改善している.(著者抄録)

シソーラス用語： *部分グラフ ,  *アルゴリズム ,  グラフ理論 ,  探索問題
準シソーラス用語： ブロックグラフ ,  *近接性探索 ,  弦グラフ ,  *多項式アルゴリズム ,  多項式遅延アルゴリズム ,  遅延アルゴリズム

分類 (1件)： ネットワーク法  (KA03040X)

引用文献 (15件)：

• Hans-Jürgen Bandelt and Henry Martyn Mulder. “Distance-hereditary graphs”. In: J. Comb. Theory, Ser. B 41.2 (1986), pp. 182-208. DOI:10.1016/0095-8956(86)90043-2.
• Caroline Brosse, Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary, and Lucas Pastor. “Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes”. In: CoRR abs/2007.01031 (2020). arXiv: 2007.01031.
• Yixin Cao. “Enumerating Maximal Induced Subgraphs”. In: 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. Ed. by Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman. Vol. 274. LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023, 31:1-31:13. DOI:10.4230/LIPIcs.ESA.2023.31.
• Frank Pok Man Chu. “A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements”. In:Inf. Process. Lett. 107.1 (2008), pp. 7-12. DOI:10.1016/J.IPL.2007.12.009.
• Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. “Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties”. In:J. Comput. Syst. Sci. 74.7 (2008), pp. 1147-1159. DOI:10.1016/j.jcss.2008.04.003.

タイトルに関連する用語 (8件)： 弦 ,  グラフ ,  クラス ,  誘導 ,  部分グラフ ,  多項式 ,  遅延 ,  アルゴリズム