木幅と関連グラフパラメータの研究

今年度の研究では,グラフパラメータを求めるためのアルゴリズムの設計や困難度の解明,および,特定のグラフクラスに対してのグラフパラメータの導出に焦点を当てた.研究成果は以下の通りである.1.カービング幅の研究:ハイパーキューブと呼ばれるグラフを一般化したグラフクラスに対して,木幅と強い関連を持つカービング幅を決定した.一般化したグラフクラスには,高次元のグリッド,トーラス,ハミンググラフなど,応用上も重要なグラフが含まれる.2.全域木混雑度の研究:前年度の結果の拡張や,k-外平面グラフに対するグラフ理論的上界の研究を行った.また,メタヒューリスティックアルゴリズムを実装し,これまでの研究で厳密な全域木混雑度が分かっているグラフやランダムグラフに対して実験を行った.この実験から,比較的直感的に優れていると考えられる幅優先的アプローチが有効である事を実験的に確認する事ができた.3.2部グラフクラスの性質の研究:一般のグラフに対して研究されている「冪」に対して,2部グラフの為の「2部冪」が知られている.本研究では,いくつかの重要なグラフクラスが2部冪に対して閉じている事を確認した.この結果は,重要な問題に対するアルゴリズム設計への応用が期待される.4.部分グラフ同型性について:部分グラフ同型性判定問題とは,与えられた二つのグラフのうち片方がもう片方を部分グラフとして含むかどうかを判定する問題である.この問題は,クリーク問題やハミルトン閉路問題など,非常に重要かつ自然な問題を部分問題として含む.この問題に対して,グラフクラスを限定した時の困難性や多項式時間可解性について,多くの結果を得る事ができた.

今年度の研究では,グラフパラメータを求めるためのアルゴリズムの設計や困難度の解明,および,特定のグラフクラスに対してのグラフパラメータの導出に焦点を当てた.研究成果は以下の通りである.1.カービング幅の研究:ハイパーキューブと呼ばれるグラフを一般化したグラフクラスに対して,木幅と強い関連を持つカービング幅を決定した.一般化したグラフクラスには,高次元のグリッド,トーラス,ハミンググラフなど,応用上も重要なグラフが含まれる.2.全域木混雑度の研究:前年度の結果の拡張や,k-外平面グラフに対するグラフ理論的上界の研究を行った.また,メタヒューリスティックアルゴリズムを実装し,これまでの研究で厳密な全域木混雑度が分かっているグラフやランダムグラフに対して実験を行った.この実験から,比較的直感的に優れていると考えられる幅優先的アプローチが有効である事を実験的に確認する事ができた.3.2部グラフクラスの性質の研究:一般のグラフに対して研究されている「冪」に対して,2部グラフの為の「2部冪」が知られている.本研究では,いくつかの重要なグラフクラスが2部冪に対して閉じている事を確認した.この結果は,重要な問題に対するアルゴリズム設計への応用が期待される.4.部分グラフ同型性について:部分グラフ同型性判定問題とは,与えられた二つのグラフのうち片方がもう片方を部分グラフとして含むかどうかを判定する問題である.この問題は,クリーク問題やハミルトン閉路問題など,非常に重要かつ自然な問題を部分問題として含む.この問題に対して,グラフクラスを限定した時の困難性や多項式時間可解性について,多くの結果を得る事ができた.