5 citations · 9 across the 16 of their papers we have counts for
6 papers · 1 filter
A Note on Using the Resistance-Distance Matrix to solve Hamiltonian Cycle Problem
Vladimir Ejov, Jerzy A Filar, Michael Haythorpe +2
An instance of Hamiltonian cycle problem can be solved by converting it to an instance of Travelling salesman problem, assigning any choice of weights to edges of the underlying gr…
A Linearly-growing Conversion from the Set Splitting Problem to the Directed Hamiltonian Cycle Problem
Michael Haythorpe, Jerzy Filar
We consider a direct conversion of the, classical, set splitting problem to the directed Hamiltonian cycle problem. A constructive procedure for such a conversion is given, and it…
Linearly-growing Reductions of Karp's 21 NP-complete Problems
Jerzy A Filar, Michael Haythorpe, Richard Taylor
We address the question of whether it may be worthwhile to convert certain, now classical, NP-complete problems to one of a smaller number of kernel NP-complete problems. In partic…
On the Determinant and its Derivatives of the Rank-one Corrected Generator of a Markov Chain on a Graph
Jerzy A Filar, Michael Haythorpe, Walter Murray
We present an algorithm to find the determinant and its first and second derivatives of a rank-one corrected generator matrix of a doubly stochastic Markov chain. The motivation ar…
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…