Statistics & OR Research Seminar
Title: Finding Happiness in Graphs: Analyses and Algorithms
Presenter: Dr Rhyd Lewis,
Date: Friday 31 May, 12:00-13:00
Keywords: Operational Research; Graph Theory; Algorithms and Heuristics; Graph Colouring
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 help tackle 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]. In this problem we are given a simple graph in which a subset of vertices have been coloured. The task is to then colour the remaining vertices such that we maximise the number of vertices that are “happy” (meaning that they have the same colour as all of their neighbours). Although this problem sounds similar to the classical graph colouring problem, structurally it is very different. Consequently, we will consider various features including the problem's complexity, methods of determining upper and lower bounds, factors that make instances difficult to solve, and some exact and heuristic-based methods.
[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.