The bottleneck 2-connected k-Steiner network problem for k 2

DOI10.1016/J.DAM.2012.01.006zbMATH Open1243.05064DBLPjournals/dam/BrazilRT12OpenAlexW2107568719WikidataQ61714616 ScholiaQ61714616MaRDI QIDQ423908FDOQ423908

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

Publication date 30 May 2012

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

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

zbMATH Keywords

exact algorithmwireless networks2-connectedblock cut-vertex decompositionbottleneck optimisationSteiner network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Distance in graphs (05C12) Network design and communication in computer systems (68M10)

Abstract: 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 $kgeq0$ 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 $kleq2$, 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}logn)$ for the cases $k=1$ and $k=2$ respectively. Our algorithms can also be extended to other norms such as the $L_p$ planes.

Recommendations

• An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes
• Bottleneck Steiner Subnetwork Problems with k-Connectivity Constraints
• On the structure and complexity of the 2-connected Steiner network problem in the plane
• Fixed parameter tractability of a biconnected bottleneck Steiner network problem
• scientific article; zbMATH DE number 4008433
• Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane
• Strong Formulations for 2-Node-Connected Steiner Network Problems
• Efficient 2-Approximation Algorithms for Computing 2-Connected Steiner Minimal Networks
• Bounding component sizes of two-connected Steiner networks
• Some New Structural Properties of Shortest 2-Connected Steiner Networks

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• scientific article; zbMATH DE number 1424548 (Why is no real title available?)
• A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• Approximations for a bottleneck Steiner tree problem
• Bottleneck Steiner trees in the plane
• Depth-First Search and Linear Graph Algorithms
• Dividing a Graph into Triconnected Components
• Exact algorithms for the bottleneck Steiner tree problem (extended abstract)
• Generalised \(k\)-Steiner tree problems in normed planes
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Minimally 2-connected graphs.
• Minimax 2-connected subgraphs and the bottleneck traveling salesman problem
• Minimum-weight two-connected spanning networks
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• The upper envelope of Voronoi surfaces and its applications

Cited in

(10)

• Survivable minimum bottleneck networks
• The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
• Fixed parameter tractability of a biconnected bottleneck Steiner network problem
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• The Euclidean bottleneck Steiner path problem
• Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane
• An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes
• Degree bounded bottleneck spanning trees in three dimensions
• On Steiner versions of (bi)connectivity in network problems
• A geometric characterisation of the quadratic min-power centre

This page was built for publication: The bottleneck 2-connected \(k\)-Steiner network problem for \(k \leq 2\)

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