@techreport{MPI-I-2002-1-003,
TITLE = {A practical minimum spanning tree algorithm using the cycle property},
AUTHOR = {Katriel, Irit and Sanders, Peter and Tr{\"a}ff, Jesper Larsson},
LANGUAGE = {eng},
NUMBER = {MPI-I-2002-1-003},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {2002},
DATE = {2002},
ABSTRACT = {We present a simple new algorithm for computing minimum spanning trees<br>that is more than two times faster than the best previously known<br>algorithms (for dense, ``difficult'' inputs). It is of conceptual interest<br>that the algorithm uses the property that the heaviest edge in a cycle can<br>be discarded. Previously this has only been exploited in asymptotically<br>optimal algorithms that are considered to be impractical. An additional <br>advantage is that the algorithm can greatly profit from pipelined memory<br>access. Hence, an implementation on a vector machine is up to 13 times<br>faster than previous algorithms. We outline additional refinements for<br>MSTs of implicitly defined graphs and the use of the central data<br>structure for querying the heaviest edge between two nodes in the MST.<br>The latter result is also interesting for sparse graphs.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}