The two-edge connectivity survivable-network design problem in planar graphs

DOI10.1145/2831235MaRDI QIDQ4962608zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, Philip N. Klein

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

planar graphspolynomial-time approximation schemesurvivable network design

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Connectivity (05C40)

Abstract: Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement) r(v) in {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min{r(u), r(v)} edge-disjoint u-to-v paths for every pair u, v of vertices. We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O(n log n). Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.

Recommendations

• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
• A PTAS for three-edge-connected survivable network design in planar graphs
• scientific article; zbMATH DE number 2086687
• Two-Connected Augmentation Problems in Planar Graphs
• Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs

Cited in

(5)

• scientific article; zbMATH DE number 2086687 (Why is no real title available?)
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
• A PTAS for three-edge-connected survivable network design in planar graphs
• Low-connectivity network design on series-parallel graphs

This page was built for publication: The two-edge connectivity survivable-network design problem in planar graphs

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