Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
From MaRDI portal
Abstract: We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is NP-complete. On the other hand, a sufficient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a second Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for constructing a second Hamiltonian decomposition and verifying vertex non-adjacency: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of computational experiments for undirected multigraphs, both backtracking algorithms lost to the known general variable neighborhood search heuristics. However, for directed multigraphs, the algorithm based on chain fixing of edges showed results comparable to heuristics on instances with an existing solution and better results on infeasible instances where the Hamiltonian decomposition does not exist.
Recommendations
Cites work
- 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
- Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes
- Error-correcting codes from permutation groups
- Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
- scientific article; zbMATH DE number 3943559 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms
- NP-completeness of some problems of partitioning and covering in graphs
- On graphs of the cone decompositions for the min-cut and max-cut problems
- 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
- Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
- Signature Methods for the Assignment Problem
- Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
- Solution of a Large-Scale Traveling-Salesman Problem
- 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 algorithm design manual
- The number of Hamiltonian decompositions of regular graphs
- The traveling salesman problem. A computational study.
- Two Algorithms for Generating Weighted Spanning Trees in Order
- Vertex adjacencies in the set covering polyhedron
Cited in
(6)- Harnack inequality for symmetric stable processes on fractals
- Harnack's inequality for stable Lévy processes
- Harnack inequalities for some Lévy processes
- Scaling invariant Harnack inequalities in a general setting
- Potential theory of truncated stable processes
- Parameterized algorithms in smooth 4-regular Hamiltonian graphs
This page was built for publication: Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870844)
