Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
type: Item
instance of: scholarly article
title: Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
author: Andrei Nikolaev
author: Egor V. Klimov
published in: Journal of Combinatorial Optimization
publication date: 2024-11-28T00:00:00Z
Mathematics Subject Classification ID: 90Cxx
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 52B05
zbMATH DE Number: 7950902
zbMATH Keywords: Hamiltonian decomposition
zbMATH Keywords: traveling salesperson polytope
zbMATH Keywords: 1-skeleton
zbMATH Keywords: integer linear programming
zbMATH Keywords: Dantzig-Fulkerson-Johnson formulation
zbMATH Keywords: Miller-Tucker-Zemlin formulation
zbMATH Keywords: subtour elimination constraints
zbMATH Keywords: edge-disjoint 2-factors
zbMATH Keywords: local search
zbMATH Keywords: variable neighborhood descent
zbMATH Keywords: chain edge fixing
MaRDI profile type: Publication
cites work: Vertex adjacencies in the set covering polyhedron
cites work: Adjacency on the constrained assignment problem
cites work: Q3514485
cites work: Q3197858
cites work: Q3425132
cites work: On pedigree polytopes and Hamiltonian cycles
cites work: Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
cites work: Error-correcting codes from permutation groups
cites work: On the Set-Covering Problem: II. An Algorithm for Set Partitioning
cites work: Signature Methods for the Assignment Problem
cites work: Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms
cites work: Combinatorial and geometric properties of the max-cut and min-cut problems
cites work: On the Skeleton of the Polytope of Pyramidal Tours
cites work: Q3844775
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: A branch and bound algorithm for symmetric 2-peripatetic salesman problems
cites work: Paths, Trees, and Flowers
cites work: Q3768703
cites work: The number of Hamiltonian decompositions of regular graphs
cites work: Q3714900
cites work: Variable neighborhood search: basics and variants
cites work: Q3858023
cites work: Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes
cites work: Simplex pivots on the set packing polytope
cites work: Reducibility among Combinatorial Problems
cites work: Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
cites work: Q4398780
cites work: Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
cites work: Q4068472
cites work: The Hirsch conjecture for the fractional stable set polytope
cites work: Integer Programming Formulation of Traveling Salesman Problems
cites work: Variable neighborhood search
cites work: On vertex adjacencies in the polytope of pyramidal tours with step-backs
cites work: Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
cites work: A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
cites work: An efficient algorithm for the minimum capacity cut problem
cites work: The adjacency relation on the traveling salesman polytope is NP-Complete
cites work: NP-completeness of some problems of partitioning and covering in graphs
cites work: Generating subtour elimination constraints for the TSP from pure integer solutions
cites work: Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
cites work: A Short Proof of the Factor Theorem for Finite Graphs
DOI: 10.1007/S10878-024-01184-0
description: scientific article; zbMATH DE number 7950902