School of Mathematics and Statistics - Theses

Permanent URI for this collection

http://hdl.handle.net/11343/295

Filters

2019 1
1
Reset filters

Settings
Statistics
Citations
Author: Andersen, Patrick ×

Search Results

Now showing 1 - 1 of 1
  • Item
    Thumbnail Image
    Degree bounded geometric spanning trees with a bottleneck objective function
    Andersen, Patrick ( 2019)
    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.