OREGON STATE UNIVERSITY

You are here

A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs

TitleA Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs
Publication TypeJournal Article
Year of Publication2009
AuthorsBorradaile, G., P. N. Klein, and C. Mathieu
JournalACM Transactions on Algorithms
Volume5
Issue3
Pagination1 - 31
Date Published07/2009
ISSN15496325
Abstract

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n).

DOI10.1145/1541885.1541892
Short TitleACM Trans. AlgorithmsTALG