TY - GEN

T1 - Node-weighted network design in planar and minor-closed families of graphs

AU - Chekuri, Chandra

AU - Ene, Alina

AU - Vakilian, Ali

N1 - Funding Information:
The authors are partially supported by NSF grant CCF-1016684.

PY - 2012

Y1 - 2012

N2 - We consider node-weighted network design in planar and minor-closed families of graphs. In particular we focus on the edge-connectivity survivable network design problem (EC-SNDP). The input consists of a node-weighted undirected graph G = (V,E) and integral connectivity requirements r(uv) for each pair of nodes uv. The goal is to find a minimum node-weighted subgraph H of G such that, for each pair uv, H contains r(uv) edge-disjoint paths between u and v. Our main result is an O(k)-approximation algorithm for EC-SNDP where k = maxuv r(uv) is the maximum requirement. This improves the O(k logn)-approximation known for node-weighted EC-SNDP in general graphs [15]. Our algorithm and analysis applies to the more general problem of covering a proper function with maximum requirement k. Our result is inspired by, and generalizes, the work of Demaine, Hajiaghayi and Klein [5] who gave constant factor approximation algorithms for node-weighted Steiner tree and Steiner forest problems (and more generally covering 0-1 proper functions) in planar and minor-closed families of graphs.

AB - We consider node-weighted network design in planar and minor-closed families of graphs. In particular we focus on the edge-connectivity survivable network design problem (EC-SNDP). The input consists of a node-weighted undirected graph G = (V,E) and integral connectivity requirements r(uv) for each pair of nodes uv. The goal is to find a minimum node-weighted subgraph H of G such that, for each pair uv, H contains r(uv) edge-disjoint paths between u and v. Our main result is an O(k)-approximation algorithm for EC-SNDP where k = maxuv r(uv) is the maximum requirement. This improves the O(k logn)-approximation known for node-weighted EC-SNDP in general graphs [15]. Our algorithm and analysis applies to the more general problem of covering a proper function with maximum requirement k. Our result is inspired by, and generalizes, the work of Demaine, Hajiaghayi and Klein [5] who gave constant factor approximation algorithms for node-weighted Steiner tree and Steiner forest problems (and more generally covering 0-1 proper functions) in planar and minor-closed families of graphs.

UR - http://www.scopus.com/inward/record.url?scp=84865280504&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865280504&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31594-7_18

DO - 10.1007/978-3-642-31594-7_18

M3 - Conference contribution

AN - SCOPUS:84865280504

SN - 9783642315930

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 206

EP - 217

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -