×

zbMATH — the first resource for mathematics

Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. (English) Zbl 1293.68308
Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 211-220 (2010).

MSC:
68W25 Approximation algorithms
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
90C39 Dynamic programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI