6 citations · 15 across the 27 of their papers we have counts for
32 papers
Simplifications to Guide Monte Carlo Tree Search in Combinatorial Games
Michael Haythorpe, Alex Newcombe, Damian O'Dea
We examine a type of modified Monte Carlo Tree Search (MCTS) for strategising in combinatorial games. The modifications are derived by analysing simplified strategies and simplifie…
A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
Zayed Asiri, Ryan Burdett, Markus Chimani +3
Determining the crossing numbers of Cartesian products of small graphs with arbitrarily large paths has been an ongoing topic of research since the 1970s. Doing so requires the est…
A Cross Entropy Approach to the Domination Problem and its Variants
Ryan Burdett, Michael Haythorpe, Alex Newcombe
The domination problem and several of its variants (total domination, 2-domination and secure domination) are considered. These problems have various real-world applications, but a…
Constructing Families of Cospectral Regular Graphs
Michael Haythorpe, Alex Newcombe
A set of graphs are called cospectral if their adjacency matrices have the same characteristic polynomial. In this paper we introduce a simple method for constructing infinite fami…
Binary Programming Formulations for the Upper Domination Problem
Ryan Burdett, Michael Haythorpe, Alex Newcombe
We consider Upper Domination, the problem of finding the minimal dominating set of maximum cardinality. Very few exact algorithms have been described for solving Upper Domination.…
Variants of the Domination Number for Flower Snarks
Ryan Burdett, Michael Haythorpe, Alex Newcombe
We consider the flower snarks, a widely studied infinite family of 3--regular graphs. For the Flower snark on vertices, it is trivial to show that the domination number…
The Secure Domination Number of Cartesian Products of Small Graphs with Paths and Cycles
Michael Haythorpe, Alex Newcombe
The secure domination numbers of the Cartesian products of two small graphs with paths or cycles is determined, as well as for Mobius ladder graphs. Prior to this work, in all case…
The maximum crossing number of
Michael Haythorpe, Alex Newcombe
We determine that the maximum crossing number of is 78, which closes the previously best known range of between 68 and 80. The proof uses several techniques which…
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…
A new benchmark set for Traveling salesman problem and Hamiltonian cycle problem
Pouya Baniasadi, Vladimir Ejov, Michael Haythorpe +1
We present a benchmark set for Traveling salesman problem (TSP) with characteristics that are different from the existing benchmark sets. In particular, we focus on small instances…
There are no Cubic Graphs on 26 Vertices with Crossing Number 10 or 11
Kieran Clancy, Michael Haythorpe, Alex Newcombe +1
We show that no cubic graphs of order 26 have crossing number larger than 9, which proves a conjecture of Ed Pegg Jr and Geoffrey Exoo that the smallest cubic graphs with crossing…
An effective crossing minimisation heuristic based on star insertion
Kieran Clancy, Michael Haythorpe, Alex Newcombe
We present a new heuristic method for minimising crossings in a graph. The method is based upon repeatedly solving the so-called {\em star insertion problem} in the setting where t…