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

DOI10.1007/978-3-642-31594-7_18zbMATH Open1272.68331arXiv1910.07616OpenAlexW1494256302MaRDI QIDQ2843249FDOQ2843249

Authors: Chandra Chekuri, Alina Ene, Ali Vakilian 

Publication date: 12 August 2013

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

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.

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

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

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)

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)