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によるブレイクスルー以後，急速に発展してきているので，今後の展開も面白そう．こういうアルゴリズム的な考え方が実際に実装できて，使えるところまで来るともっと面白い．