Mer effektive måter å finne ut av strukturen på en graf

Veikart, vennskap på sosiale media og slektstrær er bare noen få eksempler på de nettverk som finnes i våre daglige liv. Disse nettverkene, eller grafene, utgjør en måte å strukturere informasjon i livene våre, men også for bruk i algoritmer.

Rent formelt består en graf av en mengde punkt, og forbindelser mellom disse. For å prosessere grafer mer effektivt, hjelper det om grafen kan brytes opp i små biter som er forbundet med hverandre som i et tre, likt som et slektstre. Algoritmer for å lage slike oppdelinger av grafer, kalt tre-dekomposisjoner, er emnet for denne nye avhandlingen, hvor Korhonen legger frem de første forbedringene av algoritmer for dette problemet siden 1990-tallet.

Tre-dekomposisjoner har vært et viktig emne innen algoritmer og grafteori siden 1980-tallet. Hvis grafen kan brytes opp i svært små biter, så finnes det en effektiv algoritme for å lage slike tre-dekomposisjoner som har vært kjent siden 1990-tallet. Men kjøretiden på denne algoritmen skalerer svært dårlig dersom bitene må være større.

I avhandlingen tar Korhonen tak i problemet med dårlig skalering, ved at han introduserer en ny algoritmisk metode for å konstruere tre-dekomposisjoner. Denne metoden er basert på vår dype matematiske forståelse av grafteori, og viser at suboptimale tre-dekomposisjoner kan forandres litt og litt helt til de er optimale. I tillegg til å løse dette problemet, bruker Korhonen også denne metoden til å utforme nye algoritmer for andre problemer som går ut på å bryte opp grafer.

Personalia

Tuukka Korhonen er født i 1996 i Uleåborg i Finland. Han har en mastergrad i datavitenskap, tatt ved Helsingfors universitet i 2020. Han har siden september 2021 vært PhD-student i algoritme-gruppen ved Institutt for informatikk.