アルゴリズム的グラフマイナー理論

本年度は,主にセパレイターを研究した.1970年代にLIPTON-TARJANによって導入された平面グラフのセパレイターは,その後,グラフアルゴリズム分野の強力なツールとなった.例えば,平面ネットワーク上の最短パス問題などは,セパレイターの性質によるところが大きい全てのグラフがセパレイターを持つとは限らない,例えば,Expanderグラフや,密なグラフなどは,セパレイターがないことが知られている.したがってセパレイターが存在するグラフ族はなにか?という問題が,過去30年間調べられている.そして近年になって,最終的には,マイナーに関して閉じているグラフ族がセパレイターをもつある種の「限界」のグラフ族だと結論付けられているマイナーに関して閉じているグラフ族に関しては,Alon-Seymour-Thomasによる有名な結果(J.AMS&STOC'90)が知られている.彼らは,その論文の中で,具体的なセパレイターのサイズを予想した.この予想は,過去20年間でもセパレイターに関して最も注目された予想であり,いくつもの部分的結果が発表されてきた2010年度,B.Reed氏との共同研究で,この予想を完全解決した.論文は,理論計算機分野で最も権威がある国際会議であるFOCS (Annual Symposium on Foundations of Computer Science)に採択され,この会議の特集号に招待された

本年度は,主にセパレイターを研究した.1970年代にLIPTON-TARJANによって導入された平面グラフのセパレイターは,その後,グラフアルゴリズム分野の強力なツールとなった.例えば,平面ネットワーク上の最短パス問題などは,セパレイターの性質によるところが大きい全てのグラフがセパレイターを持つとは限らない,例えば,Expanderグラフや,密なグラフなどは,セパレイターがないことが知られている.したがってセパレイターが存在するグラフ族はなにか?という問題が,過去30年間調べられている.そして近年になって,最終的には,マイナーに関して閉じているグラフ族がセパレイターをもつある種の「限界」のグラフ族だと結論付けられているマイナーに関して閉じているグラフ族に関しては,Alon-Seymour-Thomasによる有名な結果(J.AMS&STOC'90)が知られている.彼らは,その論文の中で,具体的なセパレイターのサイズを予想した.この予想は,過去20年間でもセパレイターに関して最も注目された予想であり,いくつもの部分的結果が発表されてきた2010年度,B.Reed氏との共同研究で,この予想を完全解決した.論文は,理論計算機分野で最も権威がある国際会議であるFOCS (Annual Symposium on Foundations of Computer Science)に採択され,この会議の特集号に招待された