Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

DOI10.1007/978-3-642-22006-7_63zbMath1334.68303OpenAlexW4230973836MaRDI QIDQ3012847

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner tree problem on graphs: inapproximability results
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Efficient recovery from power outage (extended abstract)
• Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
• An improved LP-based approximation for steiner tree
• A threshold of ln n for approximating set cover
• Solving Connected Subgraph Problems in Wildlife Conservation
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems

This page was built for publication: Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs