MPI-I-2002-1-003

A practical minimum spanning tree algorithm using the cycle property

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

MPI-I-2002-1-003. October 2002, 21 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	479 KBytes; 324 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2002-1-003

BibTeX
@TECHREPORT{KatrielSandersTräff2002, 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},}