Modifisering av grafer: Utenfor de kjente grensene

Modifisering av grafer er et av de sentrale problemene i grafteori, og har blitt grundig studert i konteksten av parameterisert kompleksitet siden feltets begynnelse. Noen av de viktige og naturlige operasjonene ved modifisering av grafer er fjerning av noder og kanter, legge til kanter og trekke sammen kanter. Man kan for eksempel ønske å fjerne støy fra innsamlede data med slike operasjoner, slik at den gjenværende data oppfører seg pent med hensyn på modellene man ønsker å benytte.

I den første delen av avhandlingen studerer vi slike modifiseringsproblemer for ulike familier av grafer. Vi får raskere algoritmer og raske preprosseseringssteg for mange slike problemer. I noen tilfeller gir vi også matematiske bevis for ikke-eksistens av bedre algoritmer. I den andre delen av avhandlingen undersøker vi en generalisering av grafmodifisering. Igjen får vi raske algoritmer, bedre preprosseseringsalgoritmer, og påviser ikke-eksistens av visse typer algoritmer.

Personalia
Akanksha Agrawal (f. 1991) kommer fra Bhilai, Chhattisgarh, India. Hun har mastergrad i datavitenskap fra Indian Institute of Science Bangalore, Bangalore, India.