کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421214 | 684163 | 2012 | 11 صفحه PDF | دانلود رایگان |
The geometric bottleneck Steiner network problem on a set of vertices XX embedded in a normed plane requires one to construct a graph GG spanning XX and a variable set of k≥0k≥0 additional points, such that the length of the longest edge is minimised. If no other constraints are placed on GG, then a solution always exists which is a tree. In this paper, we consider the Euclidean bottleneck Steiner network problem for k≤2k≤2, where GG is constrained to be 22-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(n2)O(n2) and O(n2logn)O(n2logn) for the cases k=1k=1 and k=2k=2 respectively. Our algorithms can also be extended to other norms such as the LpLp planes.
Journal: Discrete Applied Mathematics - Volume 160, Issues 7–8, May 2012, Pages 1028–1038