Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
From MaRDI portal
Publication:2230729
Abstract: We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. A sufficient condition for vertex adjacency in the 1-skeleton of the traveling salesperson polytope can be formulated as the Hamiltonian decomposition problem in a 4-regular multigraph. We introduce a heuristic general variable neighborhood search algorithm for this problem based on finding a vertex-disjoint cycle cover of the multigraph through reduction to perfect matching and several cycle merging operations. The algorithm has a one-sided error: the answer "not adjacent" is always correct, and was tested on random directed and undirected Hamiltonian cycles and on pyramidal tours.
Recommendations
- Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
- The skeleton of the symmetric Traveling Salesman Polytope
- Interchange graphs and the Hamiltonian cycle polytope
- On the skeleton of the polytope of pyramidal tours
- On vertex adjacencies in the polytope of pyramidal tours with step-backs
Cites work
- scientific article; zbMATH DE number 3943559 (Why is no real title available?)
- A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
- A Short Proof of the Factor Theorem for Finite Graphs
- Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
- Adjacency on the order polytope with applications to the theory of fuzzy measures
- Algorithms for finding k-best perfect matchings
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Combinatorial and geometric properties of the max-cut and min-cut problems
- Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes
- Error-correcting codes from permutation groups
- Hamiltonian Cycles and Uniquely Edge Colourable Graphs
- NP-completeness of some problems of partitioning and covering in graphs
- Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms
- On pedigree polytopes and Hamiltonian cycles
- On the skeleton of the polytope of pyramidal tours
- On vertex adjacencies in the polytope of pyramidal tours with step-backs
- Optimization by simulated annealing
- Signature Methods for the Assignment Problem
- Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
- Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
- The adjacency relation on the traveling salesman polytope is NP-Complete
- The number of Hamiltonian decompositions of regular graphs
- The skeleton of the symmetric Traveling Salesman Polytope
- The travelling salesman problem and a class of polyhedra of diameter two
- Two Algorithms for Generating Weighted Spanning Trees in Order
- Variable neighborhood search
- Variable neighborhood search: basics and variants
- Variable neighbourhood search for financial derivative problem
- Vertex adjacencies in the set covering polyhedron
Cited in
(4)- On the skeleton of the polytope of pyramidal tours
- Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
- Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
- Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
This page was built for publication: Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230729)
