Algorithms for finding optimum trees: Description, use and evaluation

Algorithms for finding optimum trees: Description, use and evaluation

0.00 Avg rating0 Votes
Article ID: iaor1988208
Country: Switzerland
Volume: 13
Start Page Number: 265
End Page Number: 397
Publication Date: Aug 1988
Journal: Annals of Operations Research
Authors: , ,
Keywords: networks
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.

Reviews

Required fields are marked *. Your email address will not be published.