External Memory Minimum Spanning Trees

Dominik Schultes <mail@dominik-schultes.de>

August 2003

Bachelor thesis, Department of Computer Science, Saarland University
supervisor: Priv. Doz. Dr. Peter Sanders, Max-Planck-Institute for Computer Science

Abstract

While in the last years much theoretical work about external memory minimum spanning trees was done, the practical realization of the designed algorithms was neglected. It is the goal of my Bachelor thesis to fill this gap, i.e., we will show that the computation of minimum spanning trees of very large graphs is possible efficiently not only in theory but also in practice.

Documents

Implementation

Reference Manual (incl. Source Browsing)

Evaluation