One-Sided Monge TSP Is NP-Hard

DOI10.1007/11751595_84MaRDI QIDQ3600165zbMATH OpenOpenAlexFDO

Authors Vladimir G. Deineko, Alexander Tiskin

Publication date 10 February 2009

Published in Computational Science and Its Applications - ICCSA 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11751595_84

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Four-point conditions for the TSP: the complete complexity classification
• scientific article; zbMATH DE number 4027206
• On the traveling salesman problem with a relaxed Monge matrix
• On the recognition of permuted Supnick and incomplete Monge matrices
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time

Cited in

(2)

• Four-point conditions for the TSP: the complete complexity classification
• On the traveling salesman problem with a relaxed Monge matrix

This page was built for publication: One-Sided Monge TSP Is NP-Hard

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