7B-01
最小2部クリーク辺被覆問題が多項式時間で解ける新しいグラフクラス
○大月英明（南山大）
一般に最小2部クリーク辺被覆問題は NP-困難である．一方、2部グラフ B に対して，路重複数 R(B) がR(B)≦ 1 であれば，その最小2部クリーク辺被覆問題は多項式時間で解けることがわかっている．
ここではグラフGが2部グラフでない場合でも，その誘導部分グラフとして、ドミノ，K4，そして端点を共有する2本のコードが存在する C5 のいずれも含まない場合，その最小2部クリーク辺被覆問題は多項式時間で解けることを示す．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会