LEA

Fortgeschrittene Netzwerk- und Graph-Algorithmen (WS 09/10)

  • Dozent:
    Dr. Hanjo Täubig

  • Modul: IN2158

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

  • Zeit und Ort:
    Für die Übung am 5.2.2010 wird es kein neues Blatt geben. Sie haben aber die Gelegenheit alte Aufgaben fertigzustellen.
    Mittwoch 10:15 - 11:45 Uhr, MI Hörsaal 2
    Freitag 14:15 - 15:45 Uhr, MI Hörsaal 2

  • Übung: (Implementation der in der Vorlesung besprochenen Algorithmen)
    2 SWS Übung zur Vorlesung
    Freitag 12:15 - 13:45, Raum 03.09.034 (Praktikumsraum)
    Übungsleitung: Tobias Lieber

  • 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 / Facility Location Probleme
    • 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!)
    • 23.10.2009 (Netzwerke/Graphen, Graphrepräsentation)
    • 28.10.2009 (Wdh. DFS/BFS/Zush.komp., Zentralitätsindizes)
    • 30.10.2009 (Zentralitätsindizes)
    • 11.11.2009 (Wdh. Dijkstra/SSSP und Floyd-Warshall/APSP, Brandes-Algorithmus für Betweenness Centrality)
    • 13.11.2009 (Absolute 1-Center Problem)
    • 18.11.2009 (Algorithmus für Absolute 1-Center Problem, Minimum Diameter Spanning Tree)
    • 20.11.2009 (Algorithmus zur Berechnung der Shortcut-Werte)
    • 20.11.2009 (Zusatz: Approximation von Closeness und Betweenness Centrality, kein Prüfungsstoff!)
    • 25.11.2009 (Cliquen, besserer exponentieller Algorithmus für MaximumClique, Berechnung von Cliquen fester Größe mit Matrixmultiplikation)
    • 27.11.2009 (Aufzählung maximaler Cliquen, Strukturelle Dichte: k-Plex, k-Core, Algorithmus zur Berechnung der Core-Zahlen)
    • 09.12.2009 (Statistische Dichte, Algorithmus für DensestSubgraph-Problem)
    • 11.12.2009 (Lokale Dichte, Zusammenhang)
    • 16.12.2009 (Zusammenhang, Eigenschaften von Minimum Cuts)
    • 18.12.2009 (Minimum Cuts und Kaktus-Repräsentation)
    • 18.12.2009 (Zusatz: CNCRs und Konstruktionsalgorithmus)
    • 08.01.2010 (MinCut-Algorithmus von Stoer und Wagner, Randomisierter MinCut-Algorithmus von Karger)
    • 13.01.2010 (Gomory-Hu-Algorithmus für Equivalent Flow Trees, Anmerkung: noch nicht korrigiert)
    • 20.01.2010 (Knotenzusammenhangsalgorithmen)
    • 22.01.2010 (Kantenzusammenhangsalgorithmen, k-Kantenzusammenhangskomponenten)
    • 29.01.2010 (Zusammenhangskomponentenvielfalt, Cluster, Slicings)
    • 03.02.2010 (Länge und Weite von Slicings, Berechnung der k-Komponenten und der Zusammenhangsfunktion mit einem Narrow Slicing)

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

    • J.M. Aldous, R.J. Wilson:
      Graphs and Applications,
      The Open University / Springer, 2000.

  • Sprechstunde:
    siehe hier