The adjacency relation on the traveling salesman polytope is NP-Complete
From MaRDI portal
Publication:4153924
DOI10.1007/BF01588973zbMath0376.90067OpenAlexW2000825158MaRDI QIDQ4153924
Publication date: 1978
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01588973
Related Items
On the polytope of non-additive measures, On the complexity of some basic problems in computational convexity. I. Containment problems, On the Skeleton of the Polytope of Pyramidal Tours, Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, Adjacency of vertices of the complete pre-order polytope, Interchange graphs and the Hamiltonian cycle polytope, Some properties of the skeleton of the pyramidal tours polytope, The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract), On minimal Eulerian graphs, 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, Adjacency of the 0-1 knapsack problem, Faces with large diameter on the symmetric traveling salesman polytope, Geometry, complexity, and combinatorics of permutation polytopes, On affine reducibility of combinatorial polytopes, The common face of some 0/1-polytopes with NP-complete nonadjacency relation, Adjacency on polymatroids, Adjacency on the order polytope with applications to the theory of fuzzy measures, On pedigree polytopes and Hamiltonian cycles, On the structure of the \(k\)-additive fuzzy measures, Vertex adjacencies in the set covering polyhedron, The skeleton of the symmetric Traveling Salesman Polytope, Flip distances between graph orientations, Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration, Adjacency on the constrained assignment problem, The monotonic diameter of traveling salesman polytopes, On \({\mathbb{K}}^{\Delta}\), Some graphic uses of an even number of odd nodes, Adjacency on combinatorial polyhedra, On the facets and diameter of thek-cycle polytope, On Pedigree Polytopes and Hamiltonian Cycles, Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
Cites Work
- Unnamed Item
- Unnamed Item
- Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient
- Some simplified NP-complete graph problems
- The Euclidean traveling salesman problem is NP-complete
- On certain polytopes associated with graphs
- Gaussian elimination is not optimal
- Facets of the knapsack polytope
- The travelling salesman problem and a class of polyhedra of diameter two
- On the Computational Complexity of Combinatorial Problems
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
- P-Complete Approximation Problems
- On the Complexity of Local Search for the Traveling Salesman Problem
- Computer Solutions of the Traveling Salesman Problem
- On the Tours of a Traveling Salesman
- The Traveling Salesman Problem: A Survey
- A fundamental problem in linear inequalities with applications to the travelling salesman problem
- Matroids and the greedy algorithm
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
