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

DOI10.1016/j.ic.2012.10.017zbMath1267.68318OpenAlexW1983369141MaRDI QIDQ1951588

Carsten Moldenhauer

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.10.017

zbMATH Keywords

planar graphsapproximation algorithmsprimal-dual algorithmgeneralized Steiner treenode-weighted Steiner forestvertex feedback set

Mathematics Subject Classification ID

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)

Related Items (3)

Hitting Weighted Even Cycles in Planar Graphs ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ 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