algorithm - 我找到了一种在 O(E/V) 中计算多个 MST 的算法。这个可以发表吗？

Question

假设您使用 Kruskal 或 Prim 算法计算第一个 MST，并且您想要检查是否还有其他 MST。我可以在 O(E/V) 时间内完成。

该算法使用优先级队列(可以在 O(N) 中构造)。 Kruskal 和 Prim 已经使用优先级队列，但它们比下面列出的线性时间算法慢。

我知道已经有算法可以在线性时间内找到单个 MST:

• 随机算法可以在线性预期时间内解决它。 [Karger、Klein 和 Tarjan，“寻找最小生成树的随机线性时间算法”，J. ACM，卷。 42, 1995, pp. 321-328.]
• 如果权重是小整数，它可以在线性最坏情况下解决。 [Fredman 和 Willard，“最小生成树和最短路径的跨二分算法”，第 31 届 IEEE Symp。比较的基础。科学, 1990, pp. 719--725.]
• 否则，最佳解决方案非常接近线性但不完全是线性的。确切的界限是 O(m log beta(m,n)) 其中 beta 函数有一个复杂的定义:最小的 i 使得 log(log(log(...log(n)...))) 更小比 m/n，日志嵌套了 i 次。 [Gabow、Galil、Spencer 和 Tarjan，在无向和有向图中寻找最小生成树的高效算法。组合学，卷。 6, 1986, pp. 109--122.]

我不确定这些算法是否使用优先级队列。这并不重要，因为我可以只使用其中一种算法在 O(N) 中找到第一个 MST，然后在 O(N) 中构建优先级队列，然后在 O(E/V) 中找到所有其他 MST。总的来说，这需要 O(N)。

我刚刚想出了这个用于类作业的算法。我的助教用于查找多个 MST 的算法花费了 O(N^2) 或 O(N^3)，所以他说我应该尝试看看这是否可以发布。

编辑:我意识到我的算法只能在 O(E/V) 时间内找到其他一些 MST。我说它在 O(E/V) 时间内找到其他 MST，因为这是从特定顶点(平均)迭代所有边所需的时间。

编辑:我的证明中存在缺陷。很抱歉对此感到兴奋。

Answer 1

当然，如果它是正确的，这将是一个很好的结果。作为一个简单的健全性检查，尝试在所有边权重都设置为 1 的完整图(有一条边连接每对节点)上运行它。在这样一个有 n 个节点的图中，有 n 最小生成树。虽然为时过早，但我怀疑您的算法能否在 O(n) 时间内找到所有 n 树。但祝你好运!