Degree bounded geometric spanning trees with a bottleneck objective function

Seminar/Forum

Degree bounded geometric spanning trees with a bottleneck objective function

Room 107
Peter Hall
Monash Road

Map

More information

sanming@unimelb.edu.au

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.

Presenter

  •  Patrick Andersen
    Patrick Andersen, The University of Melbourne