Seminar 10851, Fallstudien 10852 (Winter 2003/04)
Ausgewählte graphentheoretische Probleme und Algorithmen

Aktuell

• Die Scheine sind fertiggestellt und können bei mir (Zimmer E14) abgeholt werden.
• Auf Anfrage erhalten die Seminarteilnehmer eine Zusammenstellung der Vortragsunterlagen als zip-File.

Bitte beachten Sie auch die Ankündigungen des Lehrstuhls am schwarzen Brett (je ein solches befindet sich im Mathematikgebäude im Trakt des Lehrstuhls an der Wand neben Raum E12 sowie im Informatikgebäude im Foyer vor den oberen Eingängen zum Turing-Hörsaal).

Termine und Ort

Liste aller Termine (Postscript) (PDF)

Themenliste

• Hierarchien und Beeinflussung in Netzen
  • Macht von kleinen Koalitionen
  • Einfluss in Graphen mit Kanten-Zeitstempeln
  • Routing von Verkehrsflüssen
• Übertragungsnetze und Ausfallsicherheit
  • Cost Sharing in Netzen
  • Erwartete Zielgruppen in fehlerhaften Braodcastnetzwerken
  • Zusammenhangszahl und Fehlertoleranz in gerichteten Hypergraphen
• Elementare Probleme aus der Graphentheorie
  • Schnitt mit wenigen Ecken
  • Approximationsalgorithmus für Maximum-Matching
  • Färbung mit minimaler Summe
• Anwendungen der Graphentheorie in der Biologie
  • Rekonstruktion von minimalen Wurzelbäumen
  • Platzierung von Punkten auf einer Geraden
• Heuristische Verfahren
  • k-Kürzeste Wege
  • Lokale Suchverfahren für das minimum k-cardinality tree Problem
  • Vergleich von Algorithmen für Uncapacitated Facility Location
  • Capacitated Vehicle Routing
  • Greedy versagt beim nichteuklidischen TSP
• Effiziente Datenstrukturen und amortisierte Analyse
  • Amortisierte Analyse
  • Der 2-3-Heap

Eine genauere Beschreibung der Themen mit Literaturangaben sowie Informationen zur Durchführung des Seminars finden Sie hier zum Download als Postscript- oder PDF-File.

Bei weiteren Fragen wenden Sie sich bitte per e-Mail oder persönlich an Hans-Christoph Wirth (Zimmer E14, Telefon 888-5058).