Approximation Algorithms for the Traveling Salesman Problem with Range Condition

DOI10.1051/ita:2000113zbMath0970.68196OpenAlexW2123771041MaRDI QIDQ4522112

C. Pandu Rangan, D. Arun Kumar

Publication date: 19 December 2000

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2000__34_3_173_0/

zbMATH Keywords

odd degree restricted graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

An improved upper bound for the TSP in cubic 3-edge-connected graphs

Cites Work

• The Euclidean traveling salesman problem is NP-complete
• Faster scaling algorithms for general graph matching problems
• The Traveling Salesman Problem with Distances One and Two
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item