The traveling salesman problem with few inner points

DOI10.1016/j.orl.2005.01.002zbMath1080.90064OpenAlexW2111090561MaRDI QIDQ2583717

Yanyan Li

Publication date: 18 January 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.01.002

zbMATH Keywords

traveling salesmanparameterizationexact algorithmfixed-parameter algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

On the parameterized complexity of \(d\)-dimensional point set pattern matching, Parameterized complexity of theory of mind reasoning in dynamic epistemic logic, The minimum weight triangulation problem with few inner points, A fixed parameter algorithm for optimal convex partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Euclidean traveling salesman problem is NP-complete
• The Convex-hull-and-k-line Travelling Salesman Problem
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• The prize collecting traveling salesman problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Computing and Combinatorics
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• The Traveling-Salesman Problem