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

DOI10.1007/978-3-642-31594-7_18MaRDI QIDQ2843249zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Alina Ene, Ali Vakilian

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Abstract: We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph $G=(V,E)$ and integer connectivity requirements $r(uv)$ for each unordered pair of nodes $uv$. The goal is to find a minimum weighted subgraph $H$ of $G$ such that $H$ contains $r(uv)$ disjoint paths between $u$ and $v$ for each node pair $uv$. Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP) and vertex-connectivity SNDP (VC-SNDP) depending on whether the paths are required to be edge, element or vertex disjoint respectively. Our main result is an $O(k)$-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here $k=ma{x}_{uv}r(uv)$ is the maximum connectivity requirement. This improves upon the $O(klogn)$-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [Nutov, TALG'12]. We also obtain an $O(1)$ approximation for node-weighted VC-SNDP when the connectivity requirements are in $0,1,2$; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of [Demaine, Hajiaghayi and Klein, TALG'14] who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.

Recommendations

• Primal-dual approximation algorithms for node-weighted network design in planar graphs
• Approximating Steiner networks with node-weights
• Approximating Steiner Networks with Node Weights
• Prize-collecting survivable network design in node-weighted graphs
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs

Cited in

(8)

• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Approximating Steiner networks with node-weights
• Prize-collecting survivable network design in node-weighted graphs
• Primal-dual approximation algorithms for node-weighted network design in planar graphs
• A note on iterated rounding for the survivable network design problem
• Node-weighted Network Design in Planar and Minor-closed Families of Graphs
• Approximating Steiner Networks with Node Weights
• Approximating node-weighted \(k\)-MST on planar graphs

This page was built for publication: Node-weighted network design in planar and minor-closed families of graphs

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