Nettverksdesign problemer fra et parameterisert synspunkt

Problemer med nettverksdesign dekker et bredt spekter av problemer. Disse problemene oppstår på mange områder, alt fra å skape transportnettverk til modellering av sosiale nettverk og kjemiske reaksjoner.

Motivert av behovet for å teste nettverks motstandskraft og sårbarhet, har vi studert forskjellige nettverksdesignproblemer som er klassifisert som vanskelige å løse fra et beregningsmessig kompleksitetssynspunkt.Vi så blant annet på en rettet graf som ikke er sterk og så om det var mulig å gjøre den sterk ved å legge til et gitt antall kanter fra et gitt sett med kanter.

Vi har også studert følgende problem med å fjerne kanter fra en graf. Hvis vi fikk en l-knute- koblet ikke-rettet graf, er det da mulig å fjerne et gitt antall kanter slik at resultatet forblir l-knute-koblet?For alle problemene vi har sett på, har det vist seg at parameterisert algoritmer kan løse dem. For å oppnå disse resultatene har vi funnet ulike grafteoretiske strukturer som kan være interessante i andre sammenhenger.

Personalia

Kristine Vitting Klinkby Knudsen (f. 1992) er utdannet cand.mag. ved Syddansk Universitet. Ph.d.-avhandlingen er basert på en Cotutelle-avtale mellom Universitetet i Bergen og Syddansk Universitet.