Ciaran McCreesh

Ciaran McCreesh
Are you Ciaran McCreesh?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Ciaran McCreesh
Affiliation
Location

Pubs By Year

Pub Categories

 
Computer Science - Distributed; Parallel; and Cluster Computing (4)
 
Computer Science - Data Structures and Algorithms (4)
 
Computer Science - Performance (1)
 
Computer Science - Discrete Mathematics (1)
 
Computer Science - Computational Engineering; Finance; and Science (1)
 
Computer Science - Digital Libraries (1)

Publications Authored By Ciaran McCreesh

Branch and bound searches are a common technique for solving global optimisation and decision problems, yet their irregularity, search order dependence, and the need to share bound information globally makes it challenging to implement them in parallel, and to reason about their parallel performance. We identify three key parallel search properties for replicable branch and bound implementations: Sequential Lower Bound, Non-increasing Runtimes, and Repeatability. We define a formal model for parallel branch and bound search problems and show its generality by using it to define three benchmarks: finding a Maximum Clique in a graph, 0/1 Knapsack and Travelling Salesperson (TSP). Read More

A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem. Read More

The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude. Read More

Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core thread-parallel adaptations of a state-of-the-art branch and bound algorithm for the maximum clique problem, and provide a novel explanation as to why they are successful. We show that load balance is sometimes a problem, but that the interaction of parallel search order and the most likely location of solutions within the search space is often the dominating consideration. Read More

State of the art maximum clique algorithms use a greedy graph colouring as a bound. We show that greedy graph colouring can be misleading, which has implications for parallel branch and bound. Read More

We take an existing implementation of an algorithm for the maximum clique problem and modify it so that we can distribute it over an ad-hoc cluster of machines. Our goal was to achieve a significant speedup in performance with minimal development effort, i.e. Read More