最小極大マッチング問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2008年7月3日 (木) 00:09時点における白駒 (トーク)による版 (lk)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

最小極大マッチング問題(さいしょうきょくだいまっちんぐもんだい)は、与えられたグラフ G極大マッチングの中で大きさが最小のものを見つける問題。NP困難な問題であることが知られている。

この問題に対しては、最大マッチング問題の解を求めるアルゴリズムを適用することで、近似度2 の解が得られることは容易に示すことができるが、近似度が 2 を下回るアルゴリズムは知られていない。また、2003年には、P=NP が成り立たないとき、近似度が 7/6 より良い近似アルゴリズムが存在しないことが示された。

関連項目

外部リンク