MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


A practical minimum spanning tree algorithm using the cycle property

Katriel, Irit and Sanders, Peter and Träff, Jesper Larsson

October 2002, 21 pages.

Status: available - back from printing

We present a simple new algorithm for computing minimum spanning trees that is more than two times faster than the best previously known algorithms (for dense, ``difficult'' inputs). It is of conceptual interest that the algorithm uses the property that the heaviest edge in a cycle can be discarded. Previously this has only been exploited in asymptotically optimal algorithms that are considered to be impractical. An additional advantage is that the algorithm can greatly profit from pipelined memory access. Hence, an implementation on a vector machine is up to 13 times faster than previous algorithms. We outline additional refinements for MSTs of implicitly defined graphs and the use of the central data structure for querying the heaviest edge between two nodes in the MST. The latter result is also interesting for sparse graphs.

  • Attachement: (479 KBytes); MPI-I-2002-1-003.pdf (324 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Katriel, Irit and Sanders, Peter and Tr{\"a}ff, Jesper Larsson},
  TITLE = {A practical minimum spanning tree algorithm using the cycle property},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2002-1-003},
  MONTH = {October},
  YEAR = {2002},
  ISSN = {0946-011X},