A minimum spanning tree algorithm with inverse-Ackermann type complexity

386 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Spanning trees and optimization problems (2004, methodology): “Boca Raton London New York Washington, D.C. Chapter 2”
A Kernel Two-Sample Test (2012, methodology): “The computational cost of this method using Kruskal’s algorithm isO((m+n)2 log(m+n)), although more modern methods improve on the log(m+n) term: see Chazelle (2000) for details.”
Power Watershed: A Unifying Graph-Based Optimization Framework (2011, background): “An important advantage of power watershed with varying q is that the main computational burden of these algorithms depends on an MSF computation, which is extremely efficient [21].”
Correlation structure and dynamics in volatile markets (2010, background): “Such a graph is called a minimum spanning tree (MST) [21]–[23].”
Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle (2009, background): “Therefore, we assume that the setV is the domain of a 2-dimensional image, more precisely, of a rectangular subset of Z2.”