- Artículo:
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Autor:
Mohammadhossein Bateni
Mohammadtaghi Hajiaghayi
Dániel Marx
- Resumen:
We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such ... expand
- Página:
21
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
5
- Periodo:
Octubre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-05.txt
- Documento número 1145664
- Actualizado el martes, 10 de julio de 2018 11:26:08 a. m.
- Creado el martes, 10 de julio de 2018 11:26:08 a. m.
- Enlace directo