A subset spanner for Planar graphs, : with application to subset TSP

Let ε>0 be a constant. For any edge-weighted planar graph G and a subset S of nodes of G, there is a subgraph H of G of weight a constant times that of the minimum Steiner tree for S such that distances in H between nodes in S are at most 1+ε times the corresponding distances in G. As a consequence, there is an O(n log n)-time approximation scheme for finding a TSP among a given subset of nodes of a planar graph. This is the first PTAS for the problem.

Authors

• Philip N. Klein

Keywords

• approximation scheme
• planar graph
• spanner
• traveling salesman problem