PhD defence of M. van der Wegen MSc

PhD defence: Complexity of Graph Problems: Gonality, Colouring and Scheduling

Graphs are mathematical structures that are used to model networks. A graph consists of a set of points, called vertices, and lines connecting those points, called edges. In this thesis, we study several problems on graphs. For these problems, we try to find algorithms. An algorithm is a list of instructions to solve the problem. We try to either find a fast algorithm, or to show that it is likely that such an algorithm does not exist. In this last case, we call the problem ‘hard’.

In the first part, we study ‘gonality’. This is a measure that indicates how ‘complex’ a graph is. We study several variants of gonality. We show that all variants are hard to compute, so that there are no fast algorithms for it. In the second part, we study a colouring problem for special classes of graphs. Here we want vertices to be connected by a ‘rainbow path’, that is a path in which all vertices have different colours. We give algorithms to compute a colouring with a minimum number of colours.  In the last part, we study a scheduling problem, for which we show that it is hard to determine whether a feasible schedule exists.

Start date and time
End date and time
Academiegebouw, Domplein 29 & online (link)
PhD candidate
M. van der Wegen MSc
Complexity of Graph Problems: Gonality, Colouring and Scheduling
PhD supervisor(s)
prof. dr. H.L. Bodlaender
prof. dr. G.L.M. Cornelissen
More information
Full text via Utrecht University Repository