Name
Abstract | ||
|---|---|---|
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= max uvr(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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31594-7_18 | ICALP |
Keywords | Field | DocType |
node-weighted ec-sndp,node-weighted undirected graph,proper function,minor-closed family,node-weighted steiner tree,node-weighted network design,approximation algorithm,pair uv,nodes uv,minimum node-weighted subgraph h | Graph,Discrete mathematics,Approximation algorithm,Combinatorics,Network planning and design,Steiner tree problem,Planar,Weighted network,Planar graph,Mathematics,Steiner forest | Conference |
Volume | ISSN | Citations |
7391 | 0302-9743 | 4 |
PageRank | References | Authors |
0.44 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chandra Chekuri | 1 | 3493 | 293.51 |
| Alina Ene | 2 | 409 | 25.47 |
| Ali Vakilian | 3 | 4 | 0.44 |