Vorlesungen Diskrete Strukturen Effiziente Algorithmen und Datenstrukturen I Fortgeschrittene Netzwerk- und Graph-Algorithmen Proseminar Datenkompression Hauptseminar Algorithmen für NP-schwere Probleme Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden Oberseminar

Fortgeschrittene Netzwerk- und Graph-Algorithmen (WS 2010/11)

• Dozent:
  Prof. Dr. Hanjo Täubig
• Modul: IN2158
• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  
• Zeit und Ort:
  Mo, 12:15–13:45, 00.13.009A
  Mi, 10:15–11:45, 00.08.038
• Übung:
  2 SWS Übung zur Vorlesung
  Mo, 14:00–16:00 Uhr, Raum 03.11.018
  Übungsleitung: Jeremias Weihmann
  

• Klausurtermin:
  Mittwoch, 23. Februar 2011, 11:00-13:00 Uhr, MI Hörsaal 3 (00.06.011).
  Die angegebene Zeit ist die reine Bearbeitungszeit. Anwesenheit bitte 15min vorher.
  Als Hilfsmittel ist jeweils nur ein beidseitig eigenhändig beschriebenes A4-Blatt mit Notizen zugelassen.
• Klausureinsicht:
  Mittwoch, 9.März 2011, 14:00-14:30 Uhr, Raum 01.07.014
• Wiederholungsklausur:
  Mittwoch, 27. April 2011, 15:00-17:00 Uhr, MI Hörsaal 2 (00.04.011).
• Einsicht der Wiederholungsklausur:
  Donnerstag, 5.Mai 2011, 14:00-14:30, Raum 03.11.018
• 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: (Im Falle von Fehlern freue ich mich über entsprechende Rückmeldungen!)
  • alle Slides (vorläufig / provisorisch)
  • 20.10.2010 (Netzwerke/Graphen, Graphrepräsentation)
  • 25.10.2010 (BFS, DFS, Zusammenhangskomponenten)
  • 27.10.2010 (Zentralitäten)
  • 08.11.2010 (Zentralitäten, Wdh. Alg. f. kürzeste Pfade)
  • 10.11.2010 (Wdh. Alg. f. kürzeste Pfade)
  • 15.11.2010 (Brandes-Alg. f. Betweenness-Zentralitäten, Absolute 1-center)
  • 17.11.2010 (Algorithmus für Absolute 1-center)
  • 22.11.2010 (Algorithmus für Absolute 1-center und Minimum Diameter Spanning Tree, Algorithmus für Shortcut Values)
  • 24.11.2010 (Feedback-Zentralitäten, Power Iteration)
  • 29.11.2010 (PageRank, Hubs/Authorities, Lokale Dichte, Cliquen)
  • 29.11.2010 (Zusatz: Approximation von Closeness und Betweenness Centrality, kein Prüfungsstoff!)
  • 01.12.2010 (Cliquen, Alg. f. Cliquen konstanter Größe)
  • 06.12.2010 (Aufzählung maximaler Cliquen)
  • 08.12.2010 (k-plex, k-Core)
  • 13.12.2010 (Statistisch dichte Gruppen)
  • 15.12.2010 (Statistisch dichte Gruppen, Zusammenhang)
  • 20.12.2010 (Assigment Problem, Ungarische Methode)
  • 22.12.2010 (Ungarische Methode)
  • 12.01.2011 (Zusammenhang/Sätze, Minimum Cuts)
  • 17.01.2011 (Crossing Cuts, Circular Partitions)
  • 19.01.2011 (Circular Partitions, Kaktus-Repräsentation, Stoer-Wagner-Algorithmus)
  • 19.01.2011 (Zusatz: Algorithmus zur Kaktus-Konstruktion, kein Prüfungsstoff!)
  • 24.01.2011 (Stoer-Wagner-Algorithmus, Randomisierter MinCut-Algorithmus von Karger)
  • 26.01.2011 (Gomory-Hu-Algorithmus, Knotenzusammenhangsalgorithmen)
  • 31.01.2011 (Knotenzusammenhangsalgorithmen, Kantenzusammenhangsalgorithmen)
  • 02.02.2011 (k-Kantenzusammenhangskomponenten, Zusammenhangsfunktion, Zusammenhangsvielfalt)
  • 07.02.2011 (Cluster und Subcluster)
  • 09.02.2011 (Slicings)

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

  • Smart / Slater: Center, Median, and Centroid Subgraphs (PDF)
  • Brandes: A Faster Algorithm for Betweenness Centrality
  • Kariv / Hakimi: An Algorithmic Approach to Network Location Problems. I: The p-Centers
  • Kariv / Hakimi: An Algorithmic Approach to Network Location Problems. II: The p-Medians
  • Katz: A new status index derived from sociometric analysis
  • Eppstein / Wang: Fast Approximation of Centrality
  • Eisenbrand / Grandoni: On the complexity of fixed parameter clique and dominating set
  • Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: A New Algorithm for Generating All the Maximal Independent Sets
  • David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriou: On generating all maximal independent sets
  • Seidman / Foster: A note on the potential for genuine cross-fertilization between anthropology and mathematics
  • Moon: On the diameter of a graph
  • Goldberg: Finding a maximum density subgraph
  • Kuhn: The Hungarian method for the assignment problem
  • Munkres: Algorithms for the Assignment and Transportation Problems
  • Fleischer: Building Chain and Cactus Representations of All Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time
  • Karger / Stein: A New Approach to the Minimum Cut Problem
  • Gomory / Hu: Multi-Terminal Network Flows
  • Esfahanian / Hakimi: On computing the connectivities of graphs and digraphs
  • Matula: k-Components, Clusters and Slicings in Graphs
  • Zwick: All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

  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.

  • K. Mehlhorn, P. Sanders:
    Algorithms and Data Structures - The Basic Toolbox
    Springer, 2008.

• Sprechstunde:
  siehe hier