Survivable minimum bottleneck networks

DOI10.1016/J.COMGEO.2015.06.002MaRDI QIDQ904084zbMATH OpenOpenAlexFDO

Authors C. J. Ras

Publication date 15 January 2016

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2015.06.002

zbMATH Keywords

normed (Minkowski) planesoriented Dirichlet cellspolynomial time algorithmsurvivable bottleneck Steiner networkswireless ad-hoc networks

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The author studies the problem of constructing survivable minimum bottleneck networks in normed (Minkowski) planes and presents the polynomial time algorithm for the survivable bottleneck Steiner network problem in normed planes. The method presented is applicable in any normed plane as long as a few basic operations, such as finding the intersection of two unit balls, can be performed in constant time. These results provide a significant extension of earlier works for 1-and 2-connected bottleneck networks (see [\textit{S. W. Bae} et al., Algorithmica 61, No. 4, 924--948 (2011; Zbl 1230.68203)] and [\textit{M. Brazil} et al., Discrete Appl. Math. 160, No. 7--8, 1028--1038 (2012; Zbl 1243.05064)]).

Recommendations

• An exact algorithm for the bottleneck 2-connected k-Steiner network problem in L_p planes
• Survivable network design problems in wireless networks
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
• The bottleneck 2-connected k-Steiner network problem for k 2
• Optimal and approximate bottleneck Steiner trees

Cites work

• Almost tight upper bounds for lower envelopes in higher dimensions
• An output-sensitive approach for the \(L _{1}/L _{ \infty }\) \(k\)-nearest-neighbor Voronoi diagram
• Approximations for a bottleneck Steiner tree problem
• Exact algorithms for the bottleneck Steiner tree problem
• Minimum-weight two-connected spanning networks
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• The 1-steiner tree problem
• The bottleneck 2-connected k-Steiner network problem for k 2
• The Euclidean bottleneck Steiner path problem and other applications of ( , )-pair decomposition
• The overlay of lower envelopes and its applications
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric

This page was built for publication: Survivable minimum bottleneck networks

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