Three easy special cases of the euclidean travelling salesman problem

DOI10.1051/RO/1997310403431zbMATH Open0888.90141OpenAlexW2413690630MaRDI QIDQ4372111FDOQ4372111

Authors: Vladimir G. Deineko, Jack A. A. van der Veen, Rüdiger Rudolf, Gerhard J. Woeginger 

Publication date: 8 June 1998

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/105155

Recommendations

• scientific article; zbMATH DE number 4027206
• scientific article; zbMATH DE number 34438
• Sometimes Travelling is Easy: The Master Tour Problem
• Sometimes travelling is easy: The master tour problem

zbMATH Keywords

distance matrixtravelling salesman problemKalmanson conditionsDemidenko conditionspolynomial time recognition algorithmsSupnick conditions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (9)

• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• A new tractable case of the QAP with a Robinson matrix
• On the traveling salesman problem with a relaxed Monge matrix
• Sometimes travelling is easy: The master tour problem
• Lexicographically minimizing axial motions for the Euclidean TSP
• Perspectives of Monge properties in optimization
• On the Euclidean TSP with a permuted van der Veen matrix
• Travelling salesman paths on Demidenko matrices
• Four-point conditions for the TSP: the complete complexity classification

This page was built for publication: Three easy special cases of the euclidean travelling salesman problem

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