5 citations · 9 across the 16 of their papers we have counts for
7 papers · 1 filter
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…
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…
Hamiltonian cycles and subsets of discounted occupational measures
Ali Eshragh, Jerzy A. Filar, Thomas Kalinowski +1
We study a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding pa…
Genetic Theory for Cubic Graphs
Pouya Baniasadi, Vladimir Ejov, Jerzy Filar +1
We propose a partitioning of the set of unlabelled, connected cubic graphs into two disjoint subsets named genes and descendants, where the cardinality of the descendants is much l…