Menu

Grafalgoritmer

Grafteori spiller en væsentlig rolle indenfor algoritmik, dels fordi grafer ofte optræder som underliggende model for de problemer der behandles, dels fordi grafteorien indeholder en lang række udfordrende  algoritmiske problemer. Grafer er et essentielt værktøj til at modellere en lang række praktiske problemer og algoritmisk grafteori er derfor et vigtigt område med mange praktiske anvendelser.

Grafalgoritmer undersøges i sekventielle og i parallelle versioner. Gruppen er interesseret i mange forskellige områder herunder grafsammenhæng og  udvidelse af denne gennem operationer såsom tilføjelse af kanter, samt studiet af grafklasser hvor problemer, såsom i Hamiltonkreds, klike og største uafhængige delmængde, der er NP-fuldstændige generelt, kan løses effektivt. Især er et stort antal interessante resultater blevet opnået til generalisationer af turneringer. Andre problemer undersøgt af gruppen omfatter genkendelse af forskellige grafklasser og mange varianter af graffarvningsproblemer. Gruppen er også meget interesseret i strukturelle resultater da disse ofte er det vigtigste skridt i udviklingen af en effektiv algoritme for et givet problem.

Udover eksakte algoritmer er gruppen også interesseret i heuristiske og approksimative algoritmer til grafproblemer. Vi har arbejdet på blandt andet skemalægning, graffarvning, vehicle routing, problemet med at gøre en graf 2-kant sammenhængende ved tilføjelse af færrest mulige nye kanter, problemer vedrørende disjunkte udspændende træer med vægte på kanterne og det såkaldte centrale træ problem.

Vi er også meget interesserede i anvendelser af grafalgoritmer og metodik på praktiske optimerings problemer. Specielt arbejder vi på industrielle skeduleringsproblemer, varianter af TSP problemet med anvendelser indenfor blandt andet hjemmeplejen samt anvendelser af grafalgoritmer i biologi.

Vi samarbejder og har samarbejdet med grupper fra mange universiteter, heriblandt University of Victoria, Simon Fraser University, Universite de Montpellier, Universite de Bordeaux 1, Royal Holloway University of London, Eotvos University Budapest, University of Leipzig, Universitet i Bergen.

Videnskabelige medarbejdere
Jørgen Bang-Jensen
Marco Chiarandini
Lene Monrad Favrholdt

Vi samler statistik ved hjælp af cookies for at forbedre brugeroplevelsen.  Læs mere om cookies

Acceptér cookies