A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights | Zendy

Philip N. Klein | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights

Author(s) -

Philip N. Klein

Publication year - 2008

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/060649562

Subject(s) - combinatorics , travelling salesman problem , mathematics , shortest path problem , planar , undirected graph , planar graph , enhanced data rates for gsm evolution , approximation algorithm , path (computing) , time complexity , planar straight line graph , graph , discrete mathematics , algorithm , computer science , 1 planar graph , chordal graph , computer graphics (images) , telecommunications , programming language

We give an algorithm requiring $O(c^{1/\epsilon^2}n)$ time to find an $\epsilon$-optimal traveling salesman tour in the shortest-path metric defined by an undirected planar graph with nonnegative edge-lengths. For the case of all lengths equal to 1, the time required is $O(c^{1/\epsilon} n)$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research