A polynomial-time approximation scheme for Steiner tree in planar graphs.

Glencora Borradaile Claire Kenyon-Mathieu Philip N. Klein

Published in: SODA (2007)

Keyphrases

polynomial time approximation
planar graphs
np hard
steiner tree
approximation algorithms
error bounds
bin packing
approximation guarantees
knapsack problem
special case
greedy algorithm
integer programming
undirected graph
facility location