OREGON STATE UNIVERSITY

You are here

Lecture Notes in Computer ScienceAutomata, Languages and ProgrammingThe Two-Edge Connectivity Survivable Network Problem in Planar Graphs

TitleLecture Notes in Computer ScienceAutomata, Languages and ProgrammingThe Two-Edge Connectivity Survivable Network Problem in Planar Graphs
Publication TypeBook
Year of Publication2008
AuthorsBorradaile, G., and P. N. Klein
Volume5125
Pagination485 - 501
PublisherSpringer Berlin Heidelberg
CityBerlin, Heidelberg
ISBN Number978-3-540-70575-8
ISBN1611-3349
Abstract

Consider the following problem: given a graph with edge-weights and a subset Q of vertices, find a minimum-weight 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, and arises in telecommunications applications. A more general formulation, also employed in telecommunications optimization, assigns a number (or requirement) r v  ∈ {0,1,2} to each vertex v in the graph; for each pair u,v of vertices, the solution network is required to contain min{r u , r v } edge-disjoint u-to-v paths.
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 SNP-hard in general graphs and NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O(n logn).
Under the additional restriction that the requirements are in {0,2} for vertices on the boundary of a single face of a planar graph, we give a linear-time algorithm to find the optimal solution.

DOI10.1007/978-3-540-70575-8_40