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

DOI10.1016/J.DAM.2012.01.006zbMATH Open1243.05064DBLPjournals/dam/BrazilRT12arXiv1108.3655OpenAlexW2107568719WikidataQ61714616 ScholiaQ61714616MaRDI QIDQ423908FDOQ423908

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

Publication date: 30 May 2012

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

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.

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

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

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)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• The upper envelope of Voronoi surfaces and its applications
• Title not available (Why is that?)
• Minimally 2-connected graphs.
• Dividing a Graph into Triconnected Components
• Bottleneck Steiner trees in the plane
• Minimum-weight two-connected spanning networks
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• Minimax 2-connected subgraphs and 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
• Generalised \(k\)-Steiner tree problems in normed planes
• Exact algorithms for the bottleneck Steiner tree problem (extended abstract)
• Title not available (Why is that?)
• On exact solutions to the Euclidean bottleneck Steiner tree problem

Cited In (7)

• On Steiner versions of (bi)connectivity in network problems
• A geometric characterisation of the quadratic min-power centre
• Fixed parameter tractability of a biconnected bottleneck Steiner network problem
• An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Survivable minimum bottleneck networks
• Degree bounded bottleneck spanning trees in three dimensions

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)