Primal-dual approximation algorithms for node-weighted network design in planar graphs

DOI10.1007/978-3-642-32512-0_5MaRDI QIDQ3167384zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Grigory Yaroslavtsev

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_5

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Recommendations

• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs
• Node-weighted network design in planar and minor-closed families of graphs
• Primal-dual approximation algorithms for feedback problems in planar graphs

Cited in

(5)

• Hitting weighted even cycles in planar graphs
• Node-weighted network design in planar and minor-closed families of graphs
• Node-weighted Network Design in Planar and Minor-closed Families of Graphs
• Approximating node-weighted \(k\)-MST on planar graphs
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs

This page was built for publication: Primal-dual approximation algorithms for node-weighted network design in planar graphs

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