Three easy special cases of the euclidean travelling salesman problem

DOI10.1051/RO/1997310403431MaRDI QIDQ4372111zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(9)

• Travelling salesman paths on Demidenko matrices
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• On the traveling salesman problem with a relaxed Monge matrix
• A new tractable case of the QAP with a Robinson 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
• 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)