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...
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:10500 |
| Date | 03 April 2014 |
| Creators | Meyer, Thomas William Saymoir |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
| Rights | University of Johannesburg |
Page generated in 0.0027 seconds