NY DOKTORGRAD
Optimering av grafproblemer
 Foto: Privat |
«New Width Parameters of Graphs»
I dagens samfunn er det stadig flere og større nettverk. Med nettverk mener vi for eksempel togstasjoner forbundet av toglinjer, bedrifter forbundet via forretningssamarbeid eller personer forbundet av vennskap (et slikt nettverk er Facebook). Mange interessante problemstillinger oppstår i sammenheng med ulike typer nettverk. For eksempel kan en bedrift ønske å starte kiosker på et utvalg av togstasjoner på en måte slik at de får størst mulig profit. Vi modellerer slike nettverksproblemer med grafer.
Å finne den optimale løsningen på et grafproblem ved å prøve alle løsningene kan være for mye arbeid selv for raske datamaskiner. Vi har identifisert en ny egenskap ved nettverk og funnet måter å løse mange nettverksproblemer på dersom nettverket har denne egenskapen.
Vi baserer oss på en generell strategi kalt "Divide and Conquer" som innebærer at vi først deler opp nettverket i mindre deler, finner løsningen for hver enkelt del, og tilslutt slår sammen løsninger for små nettverk for å bygge løsningen for hele nettverket. Dette er en utvidelse av tidligere teori utviklet ved hjelp av noe vi kaller "Trebredde" og hører hjemme i et felt kalt "Fixed Parameter
Tractability".
Personalia:
Martin Vatshelle er født 1982 i Bergen. Han har bachelorgrad i matematikk 2002-2006 og mastergrad i Informatikk, begge ved Universitetet i Bergen.
Tidspunkt og sted for prøveforelesningen:
08.06.2012, kl. 11.15. Oppgitt emne: «Lower bounds on treewidth for practical computing»
Sted: Lille auditorium, Høyteknologisenteret
Tidspunkt og sted for disputasen:
03.09.2012, kl. 14.15, Store auditorium, Høyteknologisenteret, Thormøhlens gate 55
Kontaktpersoner:
Martin Vatshelle, tlf: 55584176, epost: Martin.Vatshelle@uib.no
Mediekontakt ved Kommunikasjonsavdelingen
E-post: mediekontakt[ætt]uib.no
Telefon: 55 58 89 00
Avhandlingen kan lånes på Bibliotek for realfag. Avhandlingen er tilgjengelig i BORA. For kjøp/bestilling av avhandlingen, kontakt kandidaten direkte.