Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search

DOI10.1007/S10878-020-00652-7zbMATH Open1477.90088arXiv2001.04683OpenAlexW3091098346MaRDI QIDQ2230729FDOQ2230729

Authors: Andrei Nikolaev, Anna Kozlova 

Publication date: 28 September 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2001.04683

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

zbMATH Keywords

perfect matchingHamiltonian decompositionvariable neighborhood descent1-skeletonvertex adjacencygeneral variable neighborhood searchtraveling salesperson polytopevertex-disjoint cycle cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Optimization by simulated annealing
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Algorithms for finding k-best perfect matchings
• Variable neighborhood search
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• A Short Proof of the Factor Theorem for Finite Graphs
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Error-correcting codes from permutation groups
• Combinatorial and geometric properties of the max-cut and min-cut problems
• Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes
• Adjacency on the order polytope with applications to the theory of fuzzy measures
• Signature Methods for the Assignment Problem
• On pedigree polytopes and Hamiltonian cycles
• NP-completeness of some problems of partitioning and covering in graphs
• The travelling salesman problem and a class of polyhedra of diameter two
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Vertex adjacencies in the set covering polyhedron
• Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• The number of Hamiltonian decompositions of regular graphs
• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• On the skeleton of the polytope of pyramidal tours
• The skeleton of the symmetric Traveling Salesman Polytope
• Variable neighborhood search: basics and variants
• Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
• Variable neighbourhood search for financial derivative problem
• On vertex adjacencies in the polytope of pyramidal tours with step-backs
• Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope

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)