The travelling salesman problem and a class of polyhedra of diameter two

DOI10.1007/BF01585502zbMath0318.90042OpenAlexW1979802116MaRDI QIDQ4081007

No author found.

Publication date: 1974

Published in: Mathematical Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items

Adjacency on the Postman Polyhedron, Edge-Connectivity on the Assignment Polytope, On the complexity of some basic problems in computational convexity. I. Containment problems, Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm, On the Skeleton of the Polytope of Pyramidal Tours, Permutation polytopes and indecomposable elements in permutation groups, Adjacency of vertices of the complete pre-order polytope, The Boolean quadratic polytope: Some characteristics, facets and relatives, Ideal polytopes and face structures of some combinatorial optimization problems, Monotone diameter of bisubmodular polyhedra, Simple extensions of polytopes, Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes, Discrete extremal problems, Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search, A criterion for the adjacency of vertices of polytopes generated by subsets of symmetric groups, On Dantzig figures from graded lexicographic orders, On the Circuit Diameter of Some Combinatorial Polytopes, The monotonic diameter of the perfect matching and shortest path polytopes, Geometry, complexity, and combinatorics of permutation polytopes, Partial linear characterizations of the asymmetric travelling salesman polytope, Lineare Charakterisierungen von Travelling Salesman Problemen, Adjacency on polymatroids, Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors, On the symmetric travelling salesman problem I: Inequalities, The adjacency relation on the traveling salesman polytope is NP-Complete, The diameter of the stable marriage polytope: bounding from below, The monotonic diameter of traveling salesman polytopes, On the facets and diameter of thek-cycle polytope, Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions, A characterization of PM-compact Hamiltonian bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Establishing the matching polytope
• Letter to the Editor—The Multidimensional Assignment Problem
• On the Tours of a Traveling Salesman
• The Traveling Salesman Problem: A Survey
• Bottleneck extrema
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Some properties of the assignment polytope
• A fundamental problem in linear inequalities with applications to the travelling salesman problem
• On the Set-Covering Problem