LEA

Fortgeschrittene Netzwerk- und Graph-Algorithmen (WS 07/08)

  • Dozent:
    Dr. Hanjo Täubig

  • Modul: IN2158

  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)

  • Zeit und Ort:
    Montag 12:30 - 14:00 Uhr, MI Hörsaal 2
    Donnerstag 15:30 - 17:00 Uhr, MI Hörsaal 2

  • Übung: (Implementation der in der Vorlesung besprochenen Algorithmen)
    2 SWS Übung zur Vorlesung
    Freitag 14:00-15:30, Raum 03.09.034 (Praktikumsraum)

  • Hörerkreis:
    Studierende im Hauptstudium der Informatik

  • ECTS: 8 Punkte

  • Voraussetzungen:
    Stoff des Informatik Grundstudiums
    Vorlesung Effiziente Algorithmen und Datenstrukturen I/II vorteilhaft, aber nicht notwendig.

  • Inhalt:
    Ausgewählte Algorithmen aus den Gebieten
    • Zentralitätsindizes
    • Dichte in (Teil-)Graphen
    • Alternative Algorithmen für Zusammenhangsprobleme
    • Clustering
    • Netzwerk-Statistik
    • Netzwerk-Vergleich
    • Algebraische Methoden
    • Spektrale Analyse
    • Robustheit

  • Weiterführende bzw. verwandte Vorlesungen:
    Effiziente Algorithmen und Datenstrukturen I und II

  • Vorlesungsfolien: (Vorsicht, es sind bestimmt noch Fehler enthalten!)
    • 18.10.2007 (Netzwerke/Graphen, Graphrepräsentation, Standardalgorithmen)
    • 22.10.2007 (Zentralitätsindizes)
    • 25.10.2007 (Vitalitätsindizes, el. Fluss, Feedback-Zentralitäten)
    • 29.10.2007 (Zentralitätsalgorithmen)
    • 05.11.2007 (Approximation von Closeness/Betweenness, Cliquen)
    • 08.11.2007 (Cliquen: Approximation, Cliquen fester Größe, Aufzählung)
    • 12.11.2007 (Cliquen: lexikographische Aufzählung, Plex, Core)
    • 19.11.2007 (Statistisch dichte Teilgraphen)
    • 22.11.2007 (Statistisch dichte Teilgraphen, Zusammenhang)
    • 29.11.2007 (Eigenschaften von Minimum Cuts)
    • 13.12.2007 (Kaktus-Repräsentation von Minimum Cuts)
    • 17.12.2007 (Stoer/Wagner-Alg., randomisierter Kontraktionsalg. von Karger)
    • 07.01.2008 (Gomory/Hu-Bäume, lokaler Knotenzusammenhang)
    • 10.01.2008 (Knoten- und Kantenzusammenhangsalgorithmen)
    • 17.01.2008 (k-Kanten-Komponenten, Cluster)
    • 21.01.2008 (k-Kanten-Komponenten, Cluster, Slicings)
    • 24.01.2008 (Wiederholung: Matrix-Multiplikation, Transitive Hülle, APSP, EA-Folien: 21.01.08, 25.01.08)
    • 28.01.2008 (Distanzprodukt und APSP mit Rechteckiger Matrix-Multiplikation)
    • 04.02.2008 (APSP mit Rechteckiger Matrix-Multiplikation)
    • Alle Folien

  • Literatur:
    Die Vorlesung basiert auf dem Buch
    U. Brandes, Th. Erlebach (Eds.):
    Network Analysis - Methodological Foundations
    Springer, 2005.

    (Automatische Proxy-Konfiguration von http://pac.lrz-muenchen.de/ benutzen.)

    Papers:

    Weitere Bücher:

    • V. Turau:
      Algorithmische Graphentheorie,
      2. Auflage, Oldenbourg, 2004.

    • J. Bang-Jensen, G. Gutin:
      Digraphs: Theory, Algorithms and Applications,
      Springer, 2001.

    • K. Thulasiraman, M.N.S. Swamy:
      Graphs: Theory and Algorithms,
      John Wiley & Sons, 1992.

    • M. Gondran, M. Minoux:
      Graphs and Algorithms,
      John Wiley & Sons, 1984.

    • W. Kocay, D.L. Kreher:
      Graphs, Algorithms, and Optimization,
      Chapman & Hall / CRC, 2005.

    • D.E. Knuth:
      The Stanford GraphBase - A Platform for Combinatorial Computing,
      ACM Press, 1994.

    • St. Bornholdt, H.G. Schuster (Eds.):
      Handbook of Graphs and Networks - From the Genome to the Internet,
      Wiley-VCH, 2003.

    • M.C. Golumbic, I.B.-A. Hartman (Eds.):
      Graph Theory, Combinatorics and Algorithms - Interdisciplinary Applications,
      Springer, 2005.

    • G. Tinhofer, E.W. Mayr, H. Noltemayr, M.Syslo (Eds.) / R. Albrecht:
      Computational Graph Theory,
      Computing Supplementum 7, Springer, 1990.

  • Sprechstunde:
    siehe hier