A new heuristic for detecting non-Hamiltonicity in cubic graphs

DOI10.1016/j.cor.2015.06.004zbMath1349.90813arXiv1902.10342OpenAlexW1129678744MaRDI QIDQ342098

Jerzy A. Filar, Michael Haythorpe, Serguei Rossomakhine

Publication date: 17 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

polyhedraHamiltonian cyclestraveling salesman problemlinear feasibility

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Reducing the generalised Sudoku problem to the Hamiltonian cycle problem, Identification of unidentified equality constraints for integer programming problems

Uses Software

• Boost
• BGL
• GENREG

Cites Work

• Unnamed Item
• Unnamed Item
• On transition matrices of Markov chains corresponding to Hamiltonian cycles
• Polychromatic 4-coloring of cubic bipartite plane graphs
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph
• Genetic theory for cubic graphs
• Hamiltonian Cycles, Random Walks, and Discounted Occupational Measures
• A conjecture on the prevalence of cubic bridge graphs
• Almost all cubic graphs are Hamiltonian
• Fast generation of regular graphs and construction of cages
• The Traveling Salesman Problem for Cubic Graphs
• Solution of a Large-Scale Traveling-Salesman Problem