An exact algorithm for the bottleneck 2-connected k-Steiner network problem in L_p planes

2011/11/09 by Marcus Brazil, Brazil, Marcus, Charl Ras +4
Computer Science · Engineering · Mathematics · #Interconnection Networks and Systems #Mobile Ad Hoc Networks #VLSI and FPGA Design Techniques #cs.DS #math.MG #math.OC #msc:05C40 #msc:68M10

paper · pdf · doi:10.48550/arxiv.1111.2105

arxiv created 2013/10/22 · arxiv updated 2013/10/23

Abstract

We present the first exact polynomial time algorithm for constructing optimal geometric bottleneck 2-connected Steiner networks containing at most k Steiner points, where k>2 is a constant. Given a set of n vertices embedded in an L_p plane, the objective of the problem is to find a 2-connected network, spanning the given vertices and at most k additional vertices, such that the length of the longest edge is minimised. In contrast to the discrete version of this problem the additional vertices may be located anywhere in the plane. The problem is motivated by the modelling of relay-augmentation for the optimisation of energy consumption in wireless ad hoc networks. Our algorithm employs Voronoi diagrams and properties of block-cut-vertex decompositions of graphs to find an optimal solution in O(n^klog^(5k)/(2)n) steps when 1<p<∞ and in O(n²log^(7k)/(2)+1n) steps when p∈\1,∞\.

Related

• The 2-connected bottleneck Steiner network problem is NP-hard in any ℓ_p plane
• An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem
• Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
• A 2-approximation for the k-prize-collecting Steiner tree problem
• On Min-Power Steiner Tree