Minimum-weight spanning tree algorithms A survey and empirical study

摘要

The minimum-weight spanning tree problem is one of the most typical and well-known problems of combinatorial optimisation. Efficient solution techniques had been known for many years. However, in the last two decades asymptotically faster algorithms have been invented. Each new algorithm brought the time bound one step closer to linearity and finally Karger, Klein and Tarjan proposed the only known expected linear-time method. Modern algorithms make use of more advanced data structures and appear to be more complicated to implement. Most authors and practitioners refer to these but still use the classical ones, which are considerably simpler but asymptotically slower. The paper first presents a survey of the classical methods and the more recent algorithmic developments. Modern algorithms are then compared with the classical ones and their relative performance is evaluated through extensive empirical tests, using reasonably large-size problem instances. Randomly generated problem instances used in the tests range from small networks having 512 nodes and 1024 edges to quite large ones with 16 384 nodes and 524288 edges. The purpose of the comparative study is to investigate the conjecture that modern algorithms are also easy to apply and have constants of proportionality small enough to make them competitive in practice with the older ones.