Hjem
Nye doktorgrader
Ny doktorgrad

Algoritmer for grafer med strukturelle egenskaper

Paloma Thomé de Lima disputerer 27.11.2019 for ph.d.-graden ved Universitetet i Bergen med avhandlingen "Structural and Algorithmic Graph Theory Through the Lenses of Graph Classes".

Hovedinnhold

Forskningsfeltet algoritmer ligger i kjernen av informatikkfaget. En algoritme er et sett med presise instruksjoner for å løse et gitt problem, og algoritmer danner grunnmuren i alle dataprogram. En viktig gren innen algoritmeforskning dreier seg om grafalgoritmer. En graf er en matematisk struktur som kan tegnes som et sett med punkt, kalt noder, forbundet med streker, kalt kanter. En kant mellom to noder representerer en relasjon mellom dem. Grafer er en naturlig måte å modellere nettverk på, som sosiale nettverk, kommunikasjons- og transportnettverk.

Dessverre er de fleste interessante problemer på grafer vanskelige å løse, i den forstand at det er usannsynlig at det finnes en effektiv algoritme for å løse alle mulige instanser av problemet. Men mange grafer som beskriver reelle problemer har bestemte strukturer; noen ganger kan vi utnytte slik struktur for å designe effektive algoritmer.

Et eksempel er tildeling av frekvenser til radiosendere. To radiosendere som interfererer kan ikke sende på samme frekvens. Samtidig er det en begrensning på antall frekvenser vi kan bruke. Vi kan modellere dette ved å bruke en graf hvor hver radiosender er en node, og det er en kant mellom to noder hvis to radiosendere interfererer. Hvis hver frekvens blir representert med en farge, blir problemet dette: fargelegg nodene i grafen slik at noder som har en kant mellom seg får ulike farger, men bruk så få farger som mulig. På en graf med mange noder er dette en svært krevende oppgave selv når vi skal forsøke med kun tre farger.

Når det gjelder grafer som oppstår fra praktiske anvendelser av radiosender-problemet, har imidlertid disse som regel ekstra struktur, basert på for eksempel geografi. Hvorfor ikke utnytte denne strukturen for å løse disse instansene effektivt? Dette er hovedtemaet i Lima sin doktorgrad. Der undersøker hun fem vanskelige graf-problemer, og finner nye algoritmer for å løse dem effektivt for flere strukturelle egenskaper.

Personalia

Paloma T. Lima har vært doktorgradsstudent i algoritmegruppen ved Institutt for Informatikk siden oktober 2016. Hun fullførte sin bachelorgrad (2014) og mastergrad (2016) ved Federal University of Rio de Janeiro.