algorithm - 是否有一种算法可以在不重复的情况下在加权图中找到最佳的一对顶点？

Question

是否有任何有效的算法可以在具有偶数个顶点的完全加权图中找到具有以下属性的边集。

• 对于满足其他可能条件的任何集合，该集合具有最小、最大边缘权重
• 每个顶点都连接到集合中的一条边

所有权重都是正数

d我想不出比蛮力更好的方法，但我不认为它是 NP 难。

Answer 1

在多项式时间内解决这个问题的一种方法如下:

1. 在 O(E log E) 时间内对边权重进行排序
2. 对于每条边，在 ~O(E) 时间内为其分配一个伪权重 E' = 2^{position in the ordering}
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/