×

Prize-collecting Steiner problems on planar graphs. (English) Zbl 1376.68059

Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1028-1049 (2011).

MSC:

68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: Link