卒研のページ
木分解ヒューリスティックの実装と最大値独立集合問題への応用
概要
RobertsonとSeymourによって紹介されたtree-widthやHans L.Bodlaenderによって書かれたtree-decompositionの実装と最大値独立集合問題への応用を試みる。ただし。木分解の方法そのものはAire M.C.A Kosterの方法を用いて行う
卒研発表用
発表用スライド(odp)
発表用スライド(pdf)
レジュメ
string,int型のグラフウィンドウを開き"a.gw"の名でセーブすると頂点に0からラベルをつけるプログラム
string,int型の単純連結なGを生成するプログラム
minimum_separating_vertex_setを求めるプログラム
木分解するプログラム
木分解→最大値独立集合問題を解く