Hjem
Nye doktorgrader
Ny doktorgrad

Vanskelige problemer i strukturelle grafer

Reza SaeiDinvar disputerer 29. mai 2015 for ph.d.-graden ved Universitetet i Bergen med avhandlingen: "Algorithmic and combinatorial problems on graph classes".

Hovedinnhold

Grafer er en naturlig modell for å beskrive et bredt spekter av informatikkproblemer som oppstår innenfor områder som kjemi, molekylærbiologi, samfunnsfag, transportsystemer og kommunikasjonsnettverk. Dessverre er de fleste grafproblemer som er viktige og interessante fra et praktisk perspektiv ikke mulig å løse med vår kombinatoriske kunnskap og våre dataverktøy. Vi kan få en datamaskin til å løse problemene, men da ville datamaskinen brukt tusenvis av år.

Når vi lager en algoritme for å løse et problem, ønsker vi ideelt sett at den alltid skal finne en optimal løsning innen rimelig tid, uansett probleminstans. For ekstra vanskelige problemer er det ikke mulig å oppfylle alle disse tre ønskene. Siden problemene er så viktige at de ikke kan ignoreres, må vi håndtere dem på en annen måte. Å senke kravene til algoritmene våre er én mulighet. Noen ganger er tiden algoritmen bruker så kritisk at vi tillater algoritmen å gi en tilnærming til løsningen, i stedet for den optimale løsningen. En velger altså å ikke lenger garantere at algoritmen gir en optimal løsning.

I andre tilfeller er det avgjørende at løsningen er optimal, og man ønsker derfor at algoritmen gir optimale løsninger så raskt som mulig. Når vi løser praktiske tilfeller av et problem, har ofte dataene en spesifikk struktur, og det er derfor ikke nødvendig at algoritmene kan løse alle problemtilfellene. Dette gir enda en måte å løse vanskelige problemer på. Å utnytte at dataene våre har en bestemt struktur, er et viktig verktøy når man skal lage raske algoritmer. For noen problemer kan en bevise at man kan gi løsningen som en formel. Selv om en slik formel ikke eksisterer for generelle grafer, kan det være mulig å utnytte strukturen i grafklasser til å finne en formel. I SaeiDinvars avhandling studeres seks ulike grafproblemer i strukturelle grafer.

 

Personalia:

Reza SaeiDinvar (født i 1982) har vært ansatt som stipendiat i algoritmegruppen ved Institutt for Informatikk ved Universitetet i Bergen fra mai 2011. Prof. Pinar Heggernes fra Institutt for informatikk har vært hovedveileder for hans doktorgrad. SaeiDinvar tok sin bachelorgrad og mastergrad i matematikk i Tabriz, Iran.