数理科学

数理科学 2007年 04月号 [雑誌]

グラフマイナーについて河原林さんの記事が出ています．
あまりテクニカルでなく雰囲気を伝えることに主眼が置かれた内容ですが，その目的は達成できているように思えます．
ただこの特集のはじめにある中村氏の説明では「カーナビの原理の説明」が河原林さんの記事に書かれているように見えますが，これは全く正しくないので注意して下さい．

河原林さんの記事以外はまだ読んでいないけど，時間を見つけて読んでみたいです．

さて，グラフマイナー・プロジェクトといえば，RobertsonとSeymourが全20編の論文として纏め上げたグラフ理論における最大成果の1つで，河原林さんはまさにその分野の最先端にいる．
このプロジェクトの成果は理論的なものであり，実用化にはまだ遠いが，河原林さんの記事の中にあるように深遠な結果から得られるアルゴリズム的帰結は応用領域が多く，そのまま実用化されるというよりは，グラフマイナー理論による結果を指導原理としてグラフアルゴリズムの研究は進んできているように見える．
記事の中でも述べられているtreewidthやtree decompositionに関わる内容はBodlaenderらの頑張りによりかなり実用に近いところまで来ているのではないだろうか．
その他，グラフマイナー・プロジェクトが扉を開いた研究の方向性も多く，例えばグラフマイナーの結果から直ちに多項式時間アルゴリズムの存在が示される問題がたくさんある．現代の離散数学のクライマックスの1つといってもいいんじゃないだろうか．