| Engineering an External Memory Minimum Spanning Tree Algorithm (2004) | |||||||||||
Abstract | |||||||||||
| We develop an external memory algorithm for computing minimum spanning trees. The algorithm is considerably simpler than previously known external memory algorithms for this problem and needs a factor of at least four less I/Os for realistic inputs. Our implementation indicates that this algorithm processes graphs only limited by the disk capacity of most current machines in time no more than a factor 2--5 of a good internal algorithm with sufficient memory space. | |||||||||||
Publication details | |||||||||||
| |||||||||||