Vorlesungen Diskrete Strukturen Effiziente Algorithmen und Datenstrukturen I Parallele Algorithmen Fortgeschrittene Netzwerk- und Graphalgorithmen Proseminar Proofs from THE BOOK Schöne Algorithmen Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden Oberseminar

Fortgeschrittene Netzwerk- und Graph-Algorithmen (WS 2012/13)

Aktuelles

• Die Klausureinsicht der Wiederholungsklausur findet am Montag, dem 22. April, um 17:30 Uhr im Seminarraum 03.11.018 statt.

Allgemeines

• Dozent:
  Dr. Hanjo Täubig
• Modul: IN2158, TUMonline
• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  
• Zeit und Ort:
  Di, 16:15–17:45, 00.08.038
  Do, 12:15–13:45, 00.13.009A
• Übung:
  2 SWS Übung zur Vorlesung
  Übungsleitung: Jeremias Weihmann
  

• Klausurtermin:
  Dienstag, 19. Februar 2013, 14:30-17:00 Uhr, CH 22210, Ivar-Ugi-Hörsaal (in 5402 CH Laborgebäude CH 2).
  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.
  Anmeldebeginn ist Montag, der 19. November 2012.
• Wiederholungsklausur:
  Mittwoch, 10. April 2013, 14:30-17:00 Uhr, MW 0250 (Ludwig-Prandtl-Hörsaal).
  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 sowie ein Lineal zugelassen.
  Die Anmeldeperiode beginnt am Montag, dem 11. März, und endet am Montag, dem 25. März.
• Einsicht der Wiederholungsklausur:
  Montag, 22. April 2013, 17:30-19:00 Uhr, Raum 03.11.018
  Der Notenschlüssel ist:
  

  Punkte	Note
  75,5 - 80	1
  70,5 - 75	1,3
  66 - 70	1,7
  61 - 65,5	2
  56,5 - 60,5	2,3
  51,5 - 56	2,7
  46,5 - 51	3
  42 - 46	3,3
  37 - 41,5	3,7
  32 - 36,5	4
  27,5 - 31,5	4,3
  22,5 - 27	4,7
  0 - 22	5

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

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

  • R. Tarjan:
    Depth-First Search and Linear Graph Algorithms,
    SIAM Journal on Computing 1(2):146-160, 1972.
  • C. Smart / P. Slater:
    Center, Median, and Centroid Subgraphs (PDF)
    Networks 34(4):303-311, 1999.
  • U. Brandes:
    A Faster Algorithm for Betweenness Centrality
    Journal of Mathematical Sociology 25(2):163-177, 2001.
  • U. Brandes:
    On variants of shortest-path betweennesscentrality and their generic computation
    Social Networks 30(2):136-145, 2008.
  • M.E.J. Newman:
    A measure of betweenness centrality based on random walks
    Social Networks 27(1):39-54, 2005.
  • Hakimi, Schmeichel, Pierce: On p-Centers in Networks
  • 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
  • L. Katz: A new status index derived from sociometric analysis
  • Ph. Bonacich: Factoring and weighting approaches to status scores and clique identification
    Journal of Mathematical Sociology 2(1):113-120, 1972.
  • Eppstein / Wang: Fast Approximation of Centrality
  • S. Brin, L. Page:
    The anatomy of a large-scale hypertextual Web search engine
    Computer Networks and ISDN Systems 30(1-7):107-117, 1998.
  • L. Page, S. Brin, R. Motwani, T. Winograd:
    The PageRank Citation Ranking: Bringing Order to the Web
    Technical Report, Stanford InfoLab, 1999.
  • J. M. Kleinberg:
    Authoritative sources in a hyperlinked environment
    Journal of the ACM 46(5):604-632, 1999.
  • 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 graph-theoretic generalization of the clique concept
  • 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

  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