Prize-Collecting Survivable Network Design in Node-Weighted Graphs

DOI10.1007/978-3-642-32512-0_9zbMath1372.68206OpenAlexW1542228838MaRDI QIDQ3167388

Ali Vakilian, Chandra Chekuri, Alina Ene

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32512-0_9

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items

Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Covering problems in edge- and node-weighted graphs ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs