Netzwerkalgorithmen

Prof. Dr. Stefan Näher

Seminar im Hauptstudium über 2 SWS

 

Inhalt

Das Seminar beschäftigt sich mit der Theorie und der Entwicklung effizienter Algorithmen zur Behandlung verschiedener Flussprobleme und verwandter Probleme auf Graphen. Dazu behandeln wir die wichtigsten Kapitel aus dem Buch "Network Flows" von Ahuja, Magnanti, Orlin.

Teilnahmevoraussetzungen

Kenntnisse aus der Vorlesung "Algorithmen und Datenstrukturen" (Info II)
 

Literatur

Cormen, Leiserson, Rivest:
Introduction to Algorithms

Ahuja, Magnanti, Orlin:
Network Flows, Paramount Publishing International, 1993
 

Termine

16.01.2006 Vogt Kapitel  4: Label Setting: Ausarbeitung
  Reitz Kapitel  5: Label Correcting: Vortrag, Ausarbeitung
     
23.01.2006 Molly Kapitel  6: Maxflow: Grundlagen
  Sun Ying Kapitel  7: Maxflow: Polynomielle Algorithmen: Ausarbeitung
     
30.01.2006 Weber Kapitel  9: MinCostFlow: Basic Algorithms: Ausarbeitung
     
  Geier Kapitel 10: MCF: Polynomial Algorithms: Ausarbeitung
     
  Lauer Kapitel 11: MCF: Network Simplex
     
  Schumacher Kapitel 12: Assignments & Matching
     
  Yao Kapitel 13: Minimum Spanning Trees

 


Last modified on 2005-10-05 by Maria Gindorf.