6 citations · 6 across the 7 of their papers we have counts for
4 papers · 1 filter
A New Heuristic for Detecting Non-Hamiltonicity in Cubic Graphs
Jerzy A Filar, Michael Haythorpe, Serguei Rossomakhine
We analyse a polyhedron which contains the convex hull of all Hamiltonian cycles of a given undirected connected cubic graph. Our constructed polyhedron is defined by polynomially-…
Deterministic "Snakes and Ladders" Heuristic for the Hamiltonian Cycle Problem
Pouya Baniasadi, Vladimir Ejov, Jerzy A Filar +2
We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian Cycle Problem (HCP) in an undirected graph of order . Although finding a Hamiltonian cyc…
A Linear-size Conversion of HCP to 3HCP
Vladimir Ejov, Michael Haythorpe, Serguei Rossomakhine
We provide an algorithm that converts any instance of the Hamiltonian cycle problem (HCP) into a cubic instance of HCP (3HCP), and prove that the input size of the new instance is…
An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs
V. Ejov, N. Pugacheva, S. Rossomakhine +1
We propose an effective algorithm that enumerates (and actually finds) all 3-edge colorings and Hamiltonian cycles in a cubic graph. The idea is to make a preliminary run that sepa…