On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

DOI10.1016/0012-365X(81)90021-2zbMath0451.05032MaRDI QIDQ1147716

Martin Grötschel, Yoshiko Wakabayashi

Publication date: 1981

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamiltonianpolytopeasymmetric travelling salesman problemhypohamiltonian digraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (4)

On cutting-plane proofs in combinatorial optimization ⋮ Computational results on the traceability of oriented graphs of small order ⋮ The order of hypotraceable oriented graphs ⋮ Vertex degrees and 2-cuts in graphs with many Hamiltonian vertex-deleted subgraphs

Cites Work

• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• New families of hypohamiltonian graphs
• On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets
• On the structure of the monotone asymmetric travelling salesman polytope II: Hypotraceable facets
• Lineare Charakterisierungen von Travelling Salesman Problemen
• Systematic searches for hypohamiltonian graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets