Modul Graphenalgorithmen (WiSe 2011/12)

Die Übungen vom 17. Januar 2012 werden auf den 24. Januar verschoben! Die letzte Übung findet am 31. Januar statt.

Diese Veranstaltung baut auf die Inhalte des Basismoduls „Algorithmen und Datenstrukturen“ auf. Während dort grundlegende Graphalgorithmen, wie z.B. einfache Flussprobleme und bipartites Matching behandelt wurden, werden wir hier vertieft Graphenalgorithmen studieren. Wir studieren sowohl polynomielle Algorithmen wie z.B. allgemeines gewichtetes Matching, als auch NP-schwierige Graphenprobleme wie z.B. Netzwerkdesignprobleme, Färbungsprobleme und Wegeprobleme. Wir betrachten spezielle Algorithmen aber auch allgemeinere Methoden, wie z.B. Fest- Parameteralgorithmen und Methoden für Graphen mit kleiner Baumweite.

In einigen Kapiteln werden Kenntnisse der Linearen Programmierung sowie der Dualität linearer Programme, wie sie in dem Basismodul behandelt wurden, vorausgesetzt.

Kenntnisse des Basismoduls “Algorithmen und Datenstrukturen”, insbesondere Lineare Programmierung und Dualität linearer Programme (s. oben). Weiterhin gründliche Kenntnisse der mathematischen Pflichtveranstaltungen sowie der Inhalte von DAP 2 und GTI im Studiengang Informatik oder Angewandte Informatik (für BA: Algorithmen und Datenstrukturen).

• Vorlesung:
  • Dienstag, 12:15-13:45 Uhr, OH14 E02
• Beginn der Vorlesungen: Di, 11.10.
• Übungen: jede 2. Woche, dafür 4-stündig
  • Termine: Dienstag, 14:00-17:00 Uhr in OH 14 R.202
  • Beginn der Übungen: 08.11.2011

• Prüfungen: mündlich (s. Modulbeschreibung sowie Folien der ersten Vorlesung)

• Vorlesungsfolien sowie Originalartikel (englisch) (s. EWS)
• Cook, Cunningham, Pulleyblank, Schrijver,Combinatorial Optimization, John Wiley and Sons, New York, 1998

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Petra Mutzel.