Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs

DOI10.1007/978-3-642-22006-7_63MaRDI QIDQ3012847zbMATH OpenOpenAlexFDO

Authors Carsten Moldenhauer

Publication date 6 July 2011

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

Full work available at URL https://doi.org/10.1007/978-3-642-22006-7_63

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Primal-dual approximation algorithms for node-weighted network design in planar graphs
• Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Node-weighted Steiner tree and group Steiner tree in planar graphs

Cites work

• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A threshold of ln n for approximating set cover
• An O(n n) approximation scheme for Steiner tree in planar graphs
• An improved LP-based approximation for Steiner tree
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Approximation algorithms for NP-hard problems.
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• Efficient recovery from power outage (extended abstract)
• scientific article; zbMATH DE number 6783450 (Why is no real title available?)
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Solving Connected Subgraph Problems in Wildlife Conservation
• The Rectilinear Steiner Tree Problem is NP-Complete
• The Steiner tree problem on graphs: inapproximability results

Cited in

(8)

• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Node-weighted network design in planar and minor-closed families of graphs
• Primal-dual approximation algorithms for node-weighted network design in planar graphs
• Node-weighted Steiner tree and group Steiner tree in planar graphs
• Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Approximating node-weighted \(k\)-MST on planar graphs
• Approximating node-weighted \(k\)-MST on planar graphs

This page was built for publication: Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs

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