Repository logo
 

The Euclidean arborescence problem

dc.contributor.advisorKeil, Marken_US
dc.contributor.committeeMemberSrinivasan, Rajen_US
dc.contributor.committeeMemberKusalik, Anthonyen_US
dc.contributor.committeeMemberCheston, Granten_US
dc.creatorMazurek, Bradley W.en_US
dc.date.accessioned2012-05-24T10:41:12Zen_US
dc.date.accessioned2013-01-04T04:32:06Z
dc.date.available2013-05-24T08:00:00Zen_US
dc.date.available2013-01-04T04:32:06Z
dc.date.created1996en_US
dc.date.issued1996en_US
dc.date.submitted1996en_US
dc.description.abstractThe Euclidean arborescence problem involves the creation of rooted trees embedded in the plane using the L2 distance metric. These trees are interesting in that they have a low cost yet offer responsive service from the root to any other vertex. As such, arborescences have their cost compared to that of the minimum spanning tree (MST), and their radius compared to that of the shortest path tree (SPT), which are minimal with respect to cost and radius, respectively. This research examines geometric techniques for constructing such arborescences. The central component to this research is the development of a generalized arborescence algorithm framework. Independent framework modules are used to define a unique arborescence algorithm. Arborescence properties are defined, including metrics to measure the quality of the arborescence relative to the MST cost and the SPT radius. This framework is used to describe four arborescence algorithms: the circle spanning, circle Steiner, unrestricted tangent and restricted tangent arborescence algorithms. Each algorithm is analyzed to determine its computational complexity and space requirements, as well as its theoretical performance with respect to the described quality metrics. However, because theoretical bounds for metrics are not always available or reflective of practice, empirical research was done to determine how each of the algorithms perform in practice. The results of this experimentation look quite favorably on three of the four arborescence algorithms considered. The experimental values for those three have very stable and predictable quality on large point sets, which is well under a two approximation on most metrics.en_US
dc.identifier.urihttp://hdl.handle.net/10388/etd-05242012-104112en_US
dc.language.isoen_USen_US
dc.titleThe Euclidean arborescence problemen_US
dc.type.genreThesisen_US
dc.type.materialtexten_US
thesis.degree.departmentComputer Scienceen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorUniversity of Saskatchewanen_US
thesis.degree.levelMastersen_US
thesis.degree.nameMaster of Science (M.Sc.)en_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Mazurek_Bradley_W_1996_sec.pdf
Size:
5.85 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
905 B
Format:
Plain Text
Description: