| General Terms Algorithms (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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. | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||