Logspace Versions of the Theorems of Bodlaender and Courcelle

Michael Elberfeld, Andreas Jakoby, Till Tantau
ECCC TR10-062

木幅を計算するためのBodlaenderのアルゴリズムと，木幅定数の性質でMonadic Second Order Logicで書けるものを判定するCourcelleのアルゴリズムの対数領域版を示している．対数領域アルゴリズムはReingoldによるブレイクスルー以後，急速に発展してきているので，今後の展開も面白そう．こういうアルゴリズム的な考え方が実際に実装できて，使えるところまで来るともっと面白い．

授業1回目

とうとう開始．どうも丁寧さが足りなかったようなので，次回から気を付ける．おそらく準備が雑なんだと思う．はい．
授業のページは http://www.is.titech.ac.jp/~okamoto/lect/2010/dmcs/ です．

数学セミナー 5月号

数学セミナー 2010年 05月号 [雑誌]

書籍じゃないですが．．．

恥知らずにも，「フォン・ノイマン」に関する記事を書きました．情報科学的な側面を書こうと意気込んでいたのですが，ゲーム理論のことばかりになってしまいました．よろしくお願いします．