The Steiner problem in graphs and its application to phylogeny : a dissertation presented in partial fulfilment of the requirements for the degree of Master of Arts in Computer Science at Massey University

Simple item page
dc.contributor.authorShore, Malcolm Lloyd
dc.date.accessioned2018-08-28T21:28:29Z
dc.date.available2018-08-28T21:28:29Z
dc.date.issued1979
dc.description.abstractIn this thesis we consider two problems, one in Graphy Theory and the second in Evolutionary Biology. The first problem, the Steiner Problem in Graphs, belongs to the class of problems known as NP-complete. That it belongs to this class is a measure of its difficulty; if a polynomial solution can be found for the Steiner Problem in Graphs, then by definition a polynomial solution will have been found for all other NP problems. For this problem we present a solution method based upon a branch and bound approach, and we show that it complements the current methods available for solving this problem, allowing solutions to the Steiner Problem in Graphs to be calculated for any graph of size ≤ 30 points in reasonable computing time. The second problem is associated with evolution, and is an application of the Steiner Problem in Graphs. In trying to determine the evolutionary path from some common ancestor to existing species, a tree may be drawn to show these paths. This tree is called a phylogenetic tree, or phylogeny. There must be some criterion for deciding which of the many phylogenies that may be drawn most closely resembles the actual evolutionary changes. The criterion used in this thesis, used by many researchers in this area, is that of minimising the total number of changes in the phylogeny. It is shown that this problem is similar to the Steiner Problem in Graphs, and various solution methods based on heuristic graph theoretical techniques are discussed. Subsequent to this, a method of proving a phylogeny optimal is looked at, and an extension to this method presented which will allow larger phylogenies to be analysed.en_US
dc.identifier.urihttp://hdl.handle.net/10179/13628
dc.language.isoenen_US
dc.publisherMassey Universityen_US
dc.rightsThe Authoren_US
dc.subjectPhylogenyen_US
dc.subjectSteiner systemsen_US
dc.subjectGraph theoryen_US
dc.titleThe Steiner problem in graphs and its application to phylogeny : a dissertation presented in partial fulfilment of the requirements for the degree of Master of Arts in Computer Science at Massey Universityen_US
dc.typeThesisen_US
massey.contributor.authorShore, Malcolm Lloyd
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorMassey Universityen_US
thesis.degree.levelMastersen_US
thesis.degree.nameMaster of Arts (M. A.)en_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
01_front.pdf
Size:
524.57 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
02_whole.pdf
Size:
10.77 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.32 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Theses and Dissertations