ISSN:
1572-9338
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
,
Wirtschaftswissenschaften
Notizen:
Abstract This work is devoted to the problem of finding an optimum spanning tree in an undirected graph. Both min-sum and min-max trees are sought. The five algorithms considered are among the most well-known proposed in the literature. They are described in sect. 1 as thoroughly as possible, using a simplified Pascal language; all min-sum algorithms are derived from a unique prototype formulation. In sect. 2, the algorithms are implemented in PFORT to enhance their portability and ad hoc data structures are utilized in order to obtain subroutines as efficient as possible. Finally, in sect. 3, the programs are evaluated, comparing their performances in handling several classes of randomly generated graphs. Various observations are reported, and some indications for choosing the most suitable algorithm in each case are provided.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02288325
