Rhyd Lewis - Applications of Graph Theory in Operational Research

This event has ended.

Abstract:

This talk will be in two parts. In the first part I will give a brief overview of some of my research into how graph theoretical models can be used to solve (or at least approximately solve) some real-world OR problems.

The second half will be a more detailed case study on the maximum happy vertices problem, stemming from some recent work carried out with colleagues in Australia [1]. This is a new type of problem that involves determining a vertex colouring of a graph such that the number of vertices assigned to the same colour as all of their neighbours is maximised. This problem is trivial if no vertices are precoloured, though in general it is NP-hard.

[1] Lewis, R., D. Thiruvady and K. Morgan (2019) 'Finding Happiness: An Analysis of the Maximum Happy Vertices Problem'. Computers and Operations Research, vol. 103, pp. 265-276.