The traveling salesman problem with few inner points

DOI10.1016/J.ORL.2005.01.002MaRDI QIDQ2583717zbMATH OpenOpenAlexFDO

Authors 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

exact algorithmfixed-parameter algorithmparameterizationtraveling salesman

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Computing and Combinatorics
• Euclidean TSP with few inner points in linear space
• The convex-hull-and-line traveling salesman problem: A solvable case
• The Convex-hull-and-k-line Travelling Salesman Problem
• scientific article; zbMATH DE number 2080248

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• Computing and Combinatorics
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 3557795 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Convex-hull-and-k-line Travelling Salesman Problem
• The Euclidean traveling salesman problem is NP-complete
• The prize collecting traveling salesman problem
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• The traveling-salesman problem

Cited in

(21)

• A fixed parameter algorithm for optimal convex partitions
• The convex-hull-and-line traveling salesman problem: A solvable case
• The two-convex-polygons TSP: A solvable case
• Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
• Euclidean TSP on two polygons
• On the parameterized complexity of \(d\)-dimensional point set pattern matching
• The minimum weight triangulation problem with few inner points
• A polynomial algorithm for a constrained traveling salesman problem
• Euclidean TSP with few inner points in linear space
• scientific article; zbMATH DE number 3882232 (Why is no real title available?)
• scientific article; zbMATH DE number 4037195 (Why is no real title available?)
• scientific article; zbMATH DE number 1145369 (Why is no real title available?)
• Computing and Combinatorics
• The Traveling Salesman Problem with Distances One and Two
• Traversing a set of points with a minimum number of turns
• Traversing a set of points with a minimum number of turns
• Euclidean TSP in narrow strips
• Non-crossing Hamiltonian paths and cycles in output-polynomial time
• A (3/2+1/e)-approximation algorithm for ordered TSP
• Computing Hamiltonian paths with partial order restrictions
• A graph width perspective on partially ordered Hamiltonian paths and cycles ii: vertex and edge deletion numbers

This page was built for publication: The traveling salesman problem with few inner points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583717)