2026-05-12T08:48:24Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00196303 2025-01-19T22:44:16Z 6504:9795:9803

最小2部クリーク辺被覆問題が多項式時間で解ける新しいグラフクラス 大月, 英明 ソフトウェア科学・工学 一般に最小2部クリーク辺被覆問題は NP-困難である．一方、2部グラフ B に対して，路重複数 R(B) がR(B)≦ 1 であれば，その最小2部クリーク辺被覆問題は多項式時間で解けることがわかっている．ここではグラフGが2部グラフでない場合でも，その誘導部分グラフとして、ドミノ，K₄，そして端点を共有する2本のコードが存在する C₅ のいずれも含まない場合，その最小2部クリーク辺被覆問題は多項式時間で解けることを示す． conference paper 情報処理学会 2019-02-28 application/pdf 第81回全国大会講演論文集 1 2019 189 190 AN00349328 https://ipsj.ixsq.nii.ac.jp/record/196303/files/IPSJ-Z81-7B-01.pdf jpn