繰り返しのない加重グラフで、頂点の最適なペアのセットを見つけるためのアルゴリズムはありますか？

Question

偶数の頂点を持つ完全な加重グラフで、次のプロパティを持つエッジのセットを見つけるための効率的なアルゴリズムはありますか。

• セットには、可能な他の基準を肉が肉が肉質にするセットの最小の最大エッジ重量があります
• すべての頂点がセット内の正確に1つのエッジに接続されています

すべてのウェイトはプラスです

ディはブルートフォースよりも優れたものを考えることはできませんが、私はそれをNPハードとは認識していません。

Answer 1

多項式時間でこの問題を解決する1つの方法は、次のとおりです。

1. o（e log e）時間でエッジの重みを並べ替えます
2. 各エッジについて、〜o（e）時間で擬似体重e '= 2^{順序付けの位置}を割り当てます
3. O（v^3）時間のようなもので疑似体重の間の最小重量の完全な一致を見つける（選択するアルゴリズムに応じて、それは遅くなったり速くなる可能性があります）

これにより、完璧なマッチングが含まれる最大のエッジが最小限に抑えられます。これは、O（V^3）時間のようなものでまさに探しているものです。

パート3の実行方法のソースを以下に示します
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/sp10/cs598csc/lectures/lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/v.kolmogorov/papers/blossom5.ps

サンプルC ++ソースがあります http://ciju.wordpress.com/2008/08/10/min-cost-perfect-matching/

Answer 2

これを試してみてください（これを考えただけなので、最適な答えを与えるという証拠も、すべての場合に解決策を生成するかどうかもありません）：

1. 最も重い頂点V（a、b）を検索する
2. グラフから頂点Vを削除します
3. aが他の単一の頂点t（a、c）にのみ接続されている場合は、cに接続された他のすべてのエッジを削除します。これらのエッジでステップ3を繰り返します
4. Bが他の単一の頂点S（b、d）にのみ接続されている場合は、Dに接続された他のすべてのエッジを削除します。これらのエッジでステップ4を繰り返します
5. ステップ＃1から繰り返します