tot

Promotie van M. van der Wegen MSc

Promotie: Complexity of Graph Problems: Gonality, Colouring and Scheduling

Grafen zijn wiskundige structuren waarmee we netwerken kunnen modelleren. Een graaf bestaat uit een verzameling punten, knopen genoemd, en een aantal lijnen tussen deze punten, zijden genoemd. In dit proefschrift bekijken we verschillende problemen op grafen. Voor deze problemen zoeken we algoritmen. Een algoritme is een stappenplan om een probleem op te lossen. We proberen een snel algoritme te vinden, of te laten zien dat zo’n algoritme hoogstwaarschijnlijk niet bestaat. In dat laatste geval noemen we het probleem ‘moeilijk’.  

In het eerste deel kijken we naar ‘gonaliteit’. Dat is een maat die aangeeft hoe ‘ingewikkeld’ een graaf is. We bekijken verschillende varianten van gonaliteit. We laten zien dat het moeilijk is om de gonaliteit te berekenen, voor elk van de varianten. Dus dat er geen algoritmen zijn die dit snel berekenen. In het tweede deel bekijken we een kleuringsprobleem, waarin we willen dat knopen verbonden zijn door een ‘regenboogpad’. Dat is een pad waarin alle knopen verschillende kleuren hebben. We geven voor grafen met een speciale structuur een algoritme dat zo’n kleuring bepaalt met een minimaal aantal kleuren. Tot slot bekijken we een roosteringsprobleem, waarvoor we laten zien dat het moeilijk is om te bepalen of er een rooster bestaat.

Begindatum en -tijd
Einddatum en -tijd
Locatie
Academiegebouw, Domplein 29 & online (link)
Promovendus
M. van der Wegen MSc
Proefschrift
Complexity of Graph Problems: Gonality, Colouring and Scheduling
Promotor(es)
prof. dr. H.L. Bodlaender
prof. dr. G.L.M. Cornelissen
Meer informatie
Full text via Utrecht University Repository