DTU midtvejsprojekt: Metoder til at finde mindste snit i en graf
Kontakt personer:
Jens Clausen, bygning 305.218, tlf. 4525 3387, jc@imm.dtu.dk.

Beskrivelse: Mindste snit i grafer har betydning i forbindelse med separationsalgoritmer i Branch-and-Cut. Disse kan findes ved hjælp af Max Flow beregninger, men der er mindst to andre alternativer - en deterministisk algoritme byggende på en type dynamisk programmering, og en randomiseret algoritme.

De mulige fremgangsmåder skal gennemgås og analyseres, og deres kompleksitet bevises. Der skal implementeres tre af disse, og deres effektivitet skal undersøges empirisk.
Keywords:

Forudsætninger:
Ønskelige forudsætninger:
Studerende:
Periode:
DTUs elektroniske studiehåndbog: IMM tilknyttede kurser.