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

DOI10.1016/J.DAM.2015.07.029zbMATH Open1329.05268arXiv1111.2105OpenAlexW2963637014WikidataQ61714566 ScholiaQ61714566MaRDI QIDQ908293FDOQ908293

Authors: M. Brazil, C. J. Ras, D. A. Thomas 

Publication date: 4 February 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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^{k}lo{g}^{frac5k2}n)$ steps when $1<p<infty$ and in $O(n^{2}lo{g}^{frac7k2+1}n)$ steps when $pin1,infty$.

Full work available at URL: https://arxiv.org/abs/1111.2105

Recommendations

• The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\)
• Exact algorithms for the bottleneck Steiner tree problem (extended abstract)
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
• Exact algorithms for the bottleneck Steiner tree problem
• On exact solutions to the Euclidean bottleneck Steiner tree problem

zbMATH Keywords

wireless sensor networks2-connected networksbottleneck Steinerfarthest-colour Voronoi diagramsrelay augmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Network design and communication in computer systems (68M10)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• Title not available (Why is that?)
• Minimally 2-connected graphs.
• The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\)
• Bottleneck Steiner trees in the plane
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Approximations for a bottleneck Steiner tree problem
• On the structure and complexity of the 2-connected Steiner network problem in the plane
• Generalised \(k\)-Steiner tree problems in normed planes
• Title not available (Why is that?)
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• Exact algorithms for the bottleneck Steiner tree problem

Cited In (4)

• Fixed parameter tractability of a biconnected bottleneck Steiner network problem
• The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\)
• Survivable minimum bottleneck networks
• Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane

This page was built for publication: An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908293)