Open Collections

Minimal spanning trees with degree restraints

University of British Columbia

The purpose of this thesis is to develop a solution to the problem of determining the minimal spanning tree with degree restraints for a given non-directional graph. Section 1 gives an introduction to the problem. A set of definitions describing the graphical terminology used in the body of the thesis, is presented along with a description of the problem. At the end of this section a few applications of the problem are given. Section 2 outlines the method of solution used. The algorithm incorporates a branch and bound technique and this problem solving method is discussed in general in the first part of the section. Some other applications of branching and bounding are also discussed. Next, the complete algorithm is described along with a proof of optimality. A sample problem is worked through to illustrate the method of solution. Two different minimal spanning tree algorithms, one by R.C. Prim, the other by J.B. Kruskal, are used in the main core of the solution algorithm. These two approaches are discussed with the aid of a sample problem, at the end of Section 2. Computer programs were written to test the algorithms. Several sets of data were compiled for various sizes of graphs and values of degree restrictions. The results of these runs were tabulated and are discussed in Section 3. Next, a comparison is made of the method discussed here and a solution involving linear programming. Section 3 also presents some useful heuristic approaches at sub-optimization which effectively reduce the amount of computation. Section 4 summarizes the results of Section 3 and indicates the best approach to use for a specific problem.

Text

2011-06-03

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/35109

Computer Science

University of British Columbia

Graduate