Algoritmer for grafer med begrenset bredde

Algoritmeforskning ligger i datavitenskapens hjerte og sjel. En algoritme er en serie instruksjoner for å løse et problem for hånden, og algoritmer ligger sådan til grunn for alle dataprogrammer. En vesentlig del av algoritmer dreier seg om matematiske strukturer kalt grafer. En graf kan sees på som en mengde prikker, der noen par av prikker blir forbundet med streker. Grafer har viktige bruksområder i og med at de naturlig modellerer nettverk, som veinett eller sosiale nettverk. De opptrer i språkanalyse, i oppbygningen av molekyler, i nervesystemet, samhandling mellom proteiner, i kart.

Til vår ulempe er mange av de interessante problemene på grafer vanskelige å beregne, i den betydning at vi ikke kan forvente å noen gang finne en rask algoritme for å løse dem i ethvert tilfelle. Men i praksis arbeider man oftest med grafer som oppviser en eller annen form for struktur, og dette kan utnyttes i utformingen av raskere algoritmer.

Gjennom årene har man utarbeidet tusenvis (bokstavelig talt!) av ulike begrensninger på hvordan grafer kan henge sammen, og i hvert tilfelle kan man bevise om et problem kan løses raskt på slike grafer, eller om det forblir vanskelig å beregne. I den senere tid er det gjort en innsats for å forene slike resultater ved hjelp av grafdekomposisjoner med begrenset bredde. En grafdekomposisjon med begrenset bredde viser en måte å dele opp en graf i mer håndterlige biter, uten at samspillet mellom hver bit blir for innviklet. Hovedresultatene i Jaffkes avhandling åpner nye strukturelle og algoritmiske innsikter angående ulike grafdekomposisjoner.

Personalia

Lars Jaffke har vært doktorgradsstudent i algoritmegruppen ved Institutt for Informatikk siden august 2016. Han fullførte sin bachelorgrad ved Westfälische Wilhelms-Universität Münster og mastergrad ved Universiteit Utrecht.