An optimal minimum spanning tree algorithm
An optimal minimum spanning tree algorithm
复制标题
DOI：
10.1145/505241.505243
复制
发表时间：
2002-01-01
影响因子：
2.5
通讯作者：
Ramachandran, V
中科院分区：
文献类型：
--
作者：
Pettie, S;Ramachandran, V
我们建立了最小生成树问题的算法复杂度等于它的决策树复杂度。特别。我们提出了一种确定性算法，用于找到包含顶点和m条边的图的最小生成树，该树运行时间为O(T*(m, n))，其中T*是确定解决方案所需的最小边权比较次数。该算法非常简单，可以在指针机上实现。虽然我们的时间范围是最优的，但描述它的确切函数目前还不知道。目前已知的T*的最佳边界是T*(m, n) = Omega(m)和T*(m, n) = O(m - alpha(m, n))，其中alpha是Ackermann函数的某个自然逆。即使假设T-是超线性的，我们也证明了如果输入图选择在G（n,m）前面，我们的算法以高概率在线性时间内运行，无论n， in或边权的排列。该分析使用了G（n,m）的新鞅，类似于G（n,p）的边缘暴露鞅。
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically. we present a deterministic algorithm to find a minimum spanning tree of a graph within vertices and m edges that runs in time O(T*(m, n)) where T* is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine.Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for T* are T*(m, n) = Omega(m) and T*(m, n) = O(m - alpha(m, n)), where alpha is a certain natural inverse of Ackermann's function,Even under the assumption that T- is superlinear, we show that if the input graph is selected front G(n,m), our algorithm runs in linear time with high probability, regardless of n, in, or the permutation of edge weights. The analysis uses a new martingale for G(n,m), similar to the edge-exposure martingale for G(n,p).