6 citations · 15 across the 27 of their papers we have counts for
13 papers · 1 filter
An improved binary programming formulation for the secure domination problem
Ryan Burdett, Michael Haythorpe
The secure domination problem, a variation of the domination problem with some important real-world applications, is considered. Very few algorithmic attempts to solve this problem…
On the Crossing Number of the Cartesian Product of a Sunlet Graph and a Star Graph
Michael Haythorpe, Alex Newcombe
The exact crossing number is only known for a small number of families of graphs. Many of the families for which crossing numbers have been determined correspond to cartesian produ…
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…
FHCP Challenge Set: The First Set of Structurally Difficult Instances of the Hamiltonian Cycle Problem
Michael Haythorpe
The FHCP Challenge Set, comprising of 1001 instances of Hamiltonian cycle problem, is introduced. This set is the first to contain instances of Hamiltonian cycle problem for which…
Constructing Arbitrarily Large Graphs with a Specified Number of Hamiltonian Cycles
Michael Haythorpe
A constructive method is provided that outputs a directed graph which is named a broken crown graph, containing vertices and Hamiltonian cycles for any choice of integer…
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…
Non-Hamiltonian 3-Regular Graphs with Arbitrary Girth
Michael Haythorpe
It is well known that 3--regular graphs with arbitrarily large girth exist. Three constructions are given that use the former to produce non-Hamiltonian 3--regular graphs without r…
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…
On the Crossing Numbers of Cartesian Products of Small Graphs with Paths, Cycles and Stars
Kieran Clancy, Michael Haythorpe, Alex Newcombe
There has been significant research dedicated towards computing the crossing numbers of families of graphs resulting from the Cartesian products of small graphs with arbitrarily la…
A survey of graphs with known or bounded crossing numbers
Kieran Clancy, Michael Haythorpe, Alex Newcombe
We present, to the best of the authors' knowledge, all known results for the (planar) crossing numbers of specific graphs and graph families. The results are separated into various…