On minimal Eulerian graphs

DOI10.1016/0020-0190(81)90102-2zbMath0482.05046OpenAlexW2076099212MaRDI QIDQ1162523

Christos H. Papadimitriou, Mihalis Yannakakis

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90102-2

zbMATH Keywords

traveling salesman problemNP completion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Operations research and management science (90B99) Eulerian and Hamiltonian graphs (05C45)

Related Items (2)

Cliques in graphs excluding a complete graph minor ⋮ Unnamed Item

Cites Work

• On the symmetric travelling salesman problem I: Inequalities
• The Traveling Salesman Problem with Many Visits to Few Cities
• A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
• The adjacency relation on the traveling salesman polytope is NP-Complete
• On the Complexity of Local Search for the Traveling Salesman Problem
• Some Examples of Difficult Traveling Salesman Problems

This page was built for publication: On minimal Eulerian graphs