木幅と最小フィルイン問題を求めるスキームの再考
スポンサーリンク
概要
- 論文の詳細を見る
グラフとそのグラフの極小セパレータ全体からなるリストを入力としたとき、木幅と最小フィルインを求めるスキーム(極小セパレータと潜在的極大クリークに関する再帰的な関係式を基にした動的計画法)が,BouchitteとTodincaにより導入された.本論文では,このスキームの汎用化を行い,汎用化されたスキームが他のグラフパラメータに対しても有効に働くこと示す.
- 2009-10-09
著者
関連論文
- 偶グリッドのカービング幅
- 木幅と最小フィルイン問題を求めるスキームの再考
- Bipartite Permutation Graphのランダム生成と列挙
- 木幅の上界を求めるMCSアルゴリズムについて
- グラフのデカルト積における木幅の下界
- グラフのデカルト積における木幅の下界