Small and large TSP: Two polynomially solvable cases of the traveling salesman problem

DOI10.1016/0377-2217(93)90096-6zbMath0790.90071OpenAlexW2087058588MaRDI QIDQ1309942

Gerard Sierksma, Jack A. A. van der Veen, René van Dal

Publication date: 1993

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(93)90096-6

zbMATH Keywords

traveling salesmanrecognitionmachine schudulingpolynomially solvable casessubtour elimination algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Solution algorithms for synchronous flow shop problems with two dominating machines ⋮ Pyramidal tours and multiple objectives ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• The Three-Machine No-Wait Flow Shop is NP-Complete
• On general routing problems
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• On the Flow-Shop Sequencing Problem with No Wait in Process^†