強連結有向グラフ上の整合円順列(学生論文賞受賞論文要約)
スポンサーリンク
概要
- 論文の詳細を見る
強連結有向グラフの頂点はグラフの安定数以下の閉路で覆うことが出来るというGallai(1964)の予想が,Bessy-Thomasse(2004)によって肯定的に解決された.彼らは,整合円順列という概念を提案し,円順列が整合的であるときに成り立つ最大最小定理の系としてGallaiの予想を証明した.Sebo(2004)は整合円順列を求める多項式時間アルゴリズムを与えるとともに,整合円順列が与えられたグラフから最小費用流問題を解くことによってGallaiの予想を満たす安定集合と閉路被覆が得られることを示した.本研究では,Knuth(1974)による強連結グラフの分解を用いて得られる結果から整合円順列を求める効率的なアルゴリズムが導かれることを示した.また,強連結グラフの耳分解を用いて整合円順列を求めるより高速なアルゴリズムを提案した.
- 社団法人日本オペレーションズ・リサーチ学会の論文
- 2007-01-01