クリークサイズを制限した弦グラフに対する制約付きグラフ同型性判定アルゴリズム

摘要

クリークサイズを定数に制限した弦グラフに対しては，グラフ同型性判定問題（GI）が多項式時間で解けることが知られている．本論文では，クリークサイズを定数に制限した弦グラフに対して，グラフ同型性判定問題を拡張した制約付きグラフ同型性判定問題が多項式時間で解けることを示す．また，同様にグラフ同型性判定問題を拡張したPrefix Set of GIに対する多項式時間アルゴリズムを設計し，既知のアルゴリズムの時間量を改善する．