「スパニングツリー」を使用したVertex-Cover問題の2近似アルゴリズム

Vertex-Cover問題（VC、既知のNp-Complete問題）の2近似アルゴリズムに関する質問がありました。回答。問題は次のとおりです。「スパニングツリー」を使用して頂点カバー問題の2近似アルゴリズムを探します。 VCではすでに多くの欲張りのアプローチが提示されていますが、「スパニングツリー」を使用する特殊なアルゴリズムは難しいです。「スパニングツリー」を使用したVertex-Cover問題の2近似アルゴリズム

出典

2011-01-31 parsa rastegari

理論的なコンピュータサイエンス（http://cstheory.stackexchange.com/）のための別のスタックエクスチェンジがあります。そこにあなたの質問を回答する方が良いかもしれません。 –

お、ありがとうございます。私は今それをしました。 –

ええ、それは研究ではありません、私は競争のためのアルゴリズムを研究し、時には助けが必要です。誰も答えを知らないのですか？何か案が？ –

あなたは、指定されたグラフで最大一致を検索するだけで、ソリューションは最大一致を作成するノードのセットです。

出典

2011-02-01 17:51:31 ShaQ

これについて詳しく説明できますか？どのようにして辺の集合から頂点の集合に至るのですか？ – templatetypedef

これで、Max Matchingは、各頂点が他の1つの頂点または頂点のないエッジで接続されていることを保証するエッジのセットを提供します。最大のマッチングに含まれるエッジからのこの頂点のセットは、VC問題にも答えることができますが、その2近似は、最悪の場合、最適なものより2倍大きい頂点のセットを選択することができます。 – ShaQ

「スパニングツリー」を使用したVertex-Cover問題の2近似アルゴリズム

答えて

関連する問題