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