文献

J-GLOBAL ID：201702265857515996   整理番号：17A1360006

最小フィルイン問題に対する安全なセパレータについて

著者 (2件)： 小林靖明 (京大) ,  玉木久夫 (明治大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2017  号： AL-164  ページ： Vol.2017-AL-164,No.3,1-7 (WEB ONLY)  発行年： 2017年09月12日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 木幅における安全なセパレータの概念はBodlaenderとKoster(Discrete Mathematics2006)によって導入され,実用的な木幅の計算において最も重要な前処理のひとつとして知られている。本研究では,最小フィルイン問題に対する安全なセパレータを考える。グラフGのセパレータをSとし,SがクリークとなるようにGに辺を加えたグラフをG_Sとする。Sによって分離される各連結成分Wについて,W∪Sによって誘導されるG_Sの部分グラフの最小フィルイン解とG_Sにおいて加えた辺集合との和集合がGの最小フィルイン解となるとき,Sが安全なセパレータと呼ぶ。最小フィルイン問題においてセパレータが安全であるための十分条件を提案し,その条件を満たすかどうかを判定する多項式時間アルゴリズムを与える。また,最小フィルイン問題のベンチマークのインスタンスにおいて,提案手法の効果を検証するための計算機実験を行った。(著者抄録)

シソーラス用語： *アルゴリズム ,  十分条件 ,  幅 ,  *計算機シミュレーション ,  クリーク ,  計算量 ,  *無向グラフ
準シソーラス用語： 最小フィルイン問題 ,  多項式時間アルゴリズム ,  木幅計算 ,  木幅 ,  計算機実験 ,  最大クリーク ,  計算複雑性

分類 (1件)： オペレーションズリサーチ一般  (KA03010Q)

引用文献 (16件)：

• A. Agrawal, P. N. Klein, R. Ravi: Cutting down on fill using nested dissection: Provably good elimination orderings. In Proc. of Graph Theory and Sparse Matrix Computation, vol. 56 of The IMA Volumes in Mathematics and its Applications, pp. 31-55, 1993.
• D. Bergman, C. H. Cardonha, A. A. Cire, A. U. Raghunathan: On the minimum chordal completion polytope. arXiv:1612.01966, 2016.
• H. L. Bodlaender, P. Heggernes, Y. Villanger: Faster parameterized algorithms for minimum fill-in. Algorithmica 61(4), 817-838, 2011.
• V. Bouchitt?, I. Todinca: Treewidth and Minimum Fillin: Grouping the Minimal Separators. SIAM Journal on Computing 31(1), 212-232, 2001.
• V. Bouchitt?, I. Todinca: Listing all pothential maximal cliques of a graph. Theoretical Computer Science 276, 17-32, 2002.

タイトルに関連する用語 (1件)： セパレータ