Degree bounded geometric spanning trees with a bottleneck objective function
AffiliationSchool of Mathematics and Statistics
Document TypePhD thesis
Access StatusOpen Access
© 2019 Dr Patrick Andersen
We introduce the geometric $\delta$-minimum bottleneck spanning tree problem ($\delta$-MBST), which is the problem of finding a spanning tree for a set of points in a geometric space (e.g., the Euclidean plane) such that no vertex in the tree has a degree that exceeds $\delta$, and the length of the longest edge in the tree is minimum. We give complexity results for this problem and describe several approximation algorithms whose performances we investigate, both analytically and through computational experimentation.
Keywordsminimum spanning trees; bottleneck objective; approximation algorithms; discrete geometry; bounded degree; combinatorial optimisation
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References