The bottleneck 2-connected \(k\)-Steiner network problem for \(k\leq 2\)

The geometric bottleneck Steiner network problem on a set of vertices \(X\) embedded in a normed plane requires one to construct a graph \(G\) spanning \(X\) and a variable set of \(k\geq 0\) additional points, such that the length of the longest edge is minimised. If no other constraints are placed...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-08
Main Authors: Brazil, M, Ras, C J, Thomas, D A
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Euclidean geometry
Graphs
Norms
Voronoi graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The geometric bottleneck Steiner network problem on a set of vertices \(X\) embedded in a normed plane requires one to construct a graph \(G\) spanning \(X\) and a variable set of \(k\geq 0\) additional points, such that the length of the longest edge is minimised. If no other constraints are placed on \(G\) then a solution always exists which is a tree. In this paper we consider the Euclidean bottleneck Steiner network problem for \(k\leq 2\), where \(G\) is constrained to be 2-connected. By taking advantage of relative neighbourhood graphs, Voronoi diagrams, and the tree structure of block cut-vertex decompositions of graphs, we produce exact algorithms of complexity \(O(n^2)\) and \(O(n^2\log n)\) for the cases \(k=1\) and \(k=2\) respectively. Our algorithms can also be extended to other norms such as the \(L_p\) planes.
ISSN:2331-8422