Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
DOI10.1007/s10878-024-01184-0MaRDI QIDQ6645186
Andrei Nikolaev, Egor V. Klimov
Publication date: 28 November 2024
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
local searchinteger linear programmingHamiltonian decompositionvariable neighborhood descentsubtour elimination constraints1-skeletontraveling salesperson polytopechain edge fixingDantzig-Fulkerson-Johnson formulationedge-disjoint 2-factorsMiller-Tucker-Zemlin formulation
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Mathematical programming (90Cxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial and geometric properties of the max-cut and min-cut problems
- The Hirsch conjecture for the fractional stable set polytope
- Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes
- Vertex adjacencies in the set covering polyhedron
- NP-completeness of some problems of partitioning and covering in graphs
- An efficient algorithm for the minimum capacity cut problem
- Error-correcting codes from permutation groups
- Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms
- Adjacency on the constrained assignment problem
- A branch and bound algorithm for symmetric 2-peripatetic salesman problems
- Variable neighborhood search
- Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
- The number of Hamiltonian decompositions of regular graphs
- Variable neighborhood search: basics and variants
- Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
- On vertex adjacencies in the polytope of pyramidal tours with step-backs
- Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
- Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
- Generating subtour elimination constraints for the TSP from pure integer solutions
- On pedigree polytopes and Hamiltonian cycles
- Integer Programming Formulation of Traveling Salesman Problems
- Simplex pivots on the set packing polytope
- Signature Methods for the Assignment Problem
- On the Set-Covering Problem: II. An Algorithm for Set Partitioning
- Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
- The adjacency relation on the traveling salesman polytope is NP-Complete
- On the Skeleton of the Polytope of Pyramidal Tours
- Reducibility among Combinatorial Problems
- A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
- Paths, Trees, and Flowers
- Solution of a Large-Scale Traveling-Salesman Problem
- A Short Proof of the Factor Theorem for Finite Graphs
This page was built for publication: Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
