Modul Graphenalgorithmen (WiSe 2015/16)

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.

• Vorlesung:
  • Dienstag, 12:00-13:30 Uhr, Seminarraumgebäude 1 R. 1.004 (Raumtausch)
• Beginn der Vorlesungen: Dienstag, 20.10.2015
• Übungen: jede 2. Woche
  • Termine: zwei Übungsgruppen je Dienstags ab 14:00 Uhr und Donnerstags ab 12:15 Uhr in OH 14 R.202
  • Die Einteilungen Übungsgruppen wurden den Teilnehmer/inne/n via Email gesendet, sofern sie im EWS angemeldet sind. Für die anderen gilt: bitte anmelden, sonst kommen Sie weder an die Vorlesungsfolien noch an die Übungsblätter!
  • Termine der Übungen: 3.11.2015 bzw. 5.11., 24.11. bzw. 26.11., dann 14-tägig weiter

• 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.