Nye innsikter i nettverksutforskning

Hvordan kan datamaskiner på en effektiv måte utforske og forstå store og komplekse nettverk, som for eksempel internettet, sosiale medier eller transportsystemer? Emmanuel Sam sin forskning gir nye innsikter i dette spørsmålet gjennom en grundig analyse av en av de mest grunnleggende verktøyene innen informatikk: dybdeførstsøk (DFS).

DFS er en metode datamaskiner bruker for å utforske nettverk steg for steg og bygge opp et slags "kart" over forbindelser, kalt et DFS-tre. Emmanuel Sam sin forskning fokuserer på hvordan man kan finne slike DFS-trær under naturlige begrensninger som å holde høyden eller antall blader lavt. Disse spørsmålene høres kanskje enkelt ut, men de skjuler dype beregningsmessige utfordringer.

Ved bruk av verktøy fra parameterisert kompleksitet viser Sam tydelig når disse utforskningsproblemene kan løses effektivt og når de forblir vanskelige, selv for moderne datamaskiner. Et viktig gjennombrudd er en ny algoritme som gir den første eksplisitte og raske løsningen for å utforske nettverk med mål om å finne et DFS-tre med en høydebegrensning. I tillegg knytter arbeidet til Sam DFS-utforskning til andre sentrale konsepter innen informatikk som vertex cover, noe som åpner for teknikker som reduserer enkelte av problemene til mindre og mer håndterbare varianter som er enklere å løse.

Funnene har stor betydning for algoritmedesign på mange områder, inkludert nettverksdesign, logistikk, dataanalyse og kunstig intelligens, som alle er felt der nettverksutforskning og optimalisering spiller en nøkkelrolle. Oppsummert gir avhandlingen nye innsikter i beregningsstrukturer som kan brukes til å utvikle algoritmer for å løse praktiske problemer innen disse feltene.

Personalia

Emmanuel Sam, født i 1983, har bachelorgrad i matematikk fra Kwame Nkrumah University of Science and Technology, Ghana, og mastergrad i informasjonsteknologi fra Coventry University, UK. Doktorgradsprosjektet begynte i 2019 ved Institutt for Informatikk under veiledning av Nello Blaser, Michael Fellows og Helwig Hauser.