続 ISAAC 2009

2つぐらい論文を書き忘れたので書きます．

Gunnar Carlsson, Gurjeet Singh, Afra Zomorodian: Computing Multidimensional Persistence

http://dx.doi.org/10.1007/978-3-642-10631-6_74

こんなヘビーな内容がISAACに来ていいんだろうか．でも，いいと思う．
内容はcomputational topologyで，multifiltrationのpersistent homologyを多項式時間で計算するアルゴリズムの提案．普通のfiltrationの場合は1変数多項式の除算に落ちて，うまく計算できるけど，multifiltrationになると多変数多項式になるので，除算が難しくて，例えばグレブナー基底を使えばよいけど，計算量は二重指数関数的になってしまう．しかし，問題の持っている構造をうまく使うと，グレブナー基底のサイズが入力の多項式で抑えられて，なおかつ，Buchbergerのアルゴリズムも多項式時間で停止する，ということが証明できる，という流れのはなし．
発表自体ではそんな細かいことは話さずに，どちらかというとcomputational topology入門のような話になっていて，とても勉強になった．

Sylvain Guillemot, Jesper Jansson, Wing-Kin Sung: Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets

http://dx.doi.org/10.1007/978-3-642-10631-6_121

これはバイオインフォマティクスの話．たくさん系統樹があるときに，それをまとめ上げて1つの系統樹を作るという話がたくさんあるそうで，特に根付き3個組がたくさんあるときに，それらをまとめあげるにはどうするかという研究の流れの1つ．
今まで提案されている方法とは別の方法として，同じ種に対応する葉が複数あってもよいようなモデルが提案されている．ここでは，そのモデルで葉の個数を最小にする問題を考える．
結果として，この問題の複雑さ (NP困難，近似も染色数ぐらい困難) を示し，厳密アルゴリズムとしてだいたい7^nの計算量のアルゴリズムを提案している．