Back to search

University of British Columbia

Minimal spanning trees with degree restraints

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1968

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McFarlane, Archibald

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/35109

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

McFarlane, Archibald. Minimal spanning trees with degree restraints. master's thesis, University of British Columbia, 1968. http://hdl.handle.net/2429/35109