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

DOI10.1007/BF01585502zbMATH Open0318.90042OpenAlexW1979802116MaRDI QIDQ4081007FDOQ4081007

Authors:

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)

Cites Work

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

Cited In (29)

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

This page was built for publication: The travelling salesman problem and a class of polyhedra of diameter two

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