Abstract
M.Sc. (Computer Science)
Chapter 1 is a summary in which the problems- discussed in this study,
as well as the relationship between them are shown. The algorithmic
notation used when discussing the problems are also defined.
In chapter 2 the three classes of algorithms for finding a minimum
spanning tree, i.e. the algorithms of Prim, Kruskal and SolIin are
discussed. PASCAL implementations of all the algorithms are presented.
We also report on our computational experience with these implementations.
It was found that the implementation of the Prim algorithm
was very efficient, while implementations of the Kruskal algorithm
also gave good results. Implementations of the Sollin algorithm were
less efficient, because of the complex data structures involved.
Algorithms for finding an optimum arborescence or branching in a
network have independently been proposed by Edmonds, Chu & Liu as well
as Bock. Tarjan as well as Camerini et al subsequently discussed
aspects of the efficient implementation of the algorithm. In chapter 3
we draw attention to the related work of Fulkerson by reformulating
the Edmonds-Fulkerson algorithm and giving a simple proof of the
correctness of the algorithm. We also discuss and present an implementation
of the algorithm and report on our computational experience.
From the results presented it is clear that the number of cycles
encountered during the first phase of the algorithm has a significant
effect on the efficiency of the algorithm...