最小極大マッチング問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 最小極大マッチング問題の意味・解説 

最小極大マッチング問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/06/08 02:03 UTC 版)

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

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

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「最小極大マッチング問題」の関連用語

最小極大マッチング問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



最小極大マッチング問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの最小極大マッチング問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS