Kopf
Fakultät für Informatik
Lehrstuhl für Algorithm Engineering (Ls11)
Home Kontakt Deutsch English
menu-en

 

Proseminar "Graphen und Netzwerke"

Das Proseminar "Graphen und Netzwerke wird im Sommersemester 2007 von Dennis Berk, Fabian Gieseke und Prof. Dr. Jan Vahrenhold angeboten.

Das Vorlesungsverzeichnis enthält die Belegnummer und die offiziellen Kommentare zur Veranstaltung (Information noch nicht verfügbar).

 


Aktuelle Informationen

Bitte beachten Sie, dass die nachfolgenden Informationen noch vorläufig sind und ggfs. in der ersten Vorlesungswoche aktualisiert werden können.

  • (11.06.07) Das von Philipp Gerloff erstellte Programm "TGT - Theta-Graph Toolkit" ist hier zu finden.
  • (12.06.07) Die Vorträge (12) und (13) fallen ersatzlos aus.
  • (17.04.07) Die Vorträge (4),(9) und (10) fallen ersatzlos aus.
  • (06.02.07) Die Vortragsthemen und -termine stehen fest.
  • (24.01.07) Die Folien der Vorbesprechung sind hier zu finden.
  • (10.01.07) Die Vorbesprechung für das Proseminar findet am 24.01.07 um 16:15 Uhr im Seminarraum 202 (OH-14) statt.

 


Zeit und Ort

  • Seminar: Dienstags, 14:15-16:15 Uhr.
  • Ort: Seminarraum 202, OH-14.

Datum

Vortrag

Abgabe
der Folienentwürfe

03.04.2007

(1)

20.03.2007

10.04.2007

(2)

27.03.2007

17.04.2007

(3)

03.04.2007

24.04.2007

(4)

10.04.2007

08.05.2007

(5), (6)

24.04.2007

15.05.2007

(7)

02.05.2007

22.05.2007

(8)

08.05.2007

29.05.2007

(9)

15.05.2007

05.06.2007

(10)

22.05.2007

12.06.2007

(11)

29.05.2007

19.06.2007

(12)

05.06.2007

26.06.2007

(13)

12.06.2007

03.07.2007

(14)

19.06.2007

10.07.2007

(15)

26.06.2007

 


Zuordnung

  • Diplomstudiengang Informatik.
  • Diplomstudiengang Angewandte Informatik.
  • Studiengang "Lehramt Informatik" mit dem Abschluss "Erste Staatsprüfung"
  • Modellversuch "Gestufte Studiengänge in der Lehrerbildung".

 


Inhalt

In diesem Proseminar werden wir uns mit Themen aus dem Umfeld der Algorithmischen Graphentheorie beschäftigen, die die in der Vorlesung DAP II besprochenen Inhalte aufgreifen und vertiefen. Hierbei werden die folgenden Themenfelder behandelt:

  • Algorithmen für geometrische Netzwerke.
  • Algorithmen für (Euklidische) Spanner-Graphen.
  • Soziale Netzwerke und Methoden zu ihrer Analyse.

Geometrische Netzwerke bilden Konstrukte der realen Welt auf gewichtete Graphen ab, die so in die Ebene eingebettet sind, dass die Kantengewichte den Kosten für das Nutzen eine Verbindung entsprechen. Beispiele für solche Netzwerke sind Transportnetzwerke, in denen die Koste für das Befahren einer Straße proportional zur ihrer Länge sind. Graphen, in denen relativ gesehen nur eingeschränkte Umwege im Vergleich zu einer direkten Verbindung auftreten, werden als "Spanner-Graphen" bezeichnet.

Soziale Netzwerke bilden Beziehungen zwischen Personen oder Gruppen auf Graphen ab. Bei der Analyse solcher Netzwerke wird beispielsweise untersucht, wie sich Ansteckungskrankheiten ausbreiten, wie sich (formale oder informale) Kommunikationswege in Unternehmen gestalten, oder wie bedeutend einzelne Akteure für das Gesamtgefüge sind.

 


Vortragsthemen

  1. Einführung in die Themengebiete (GN/SNA) [NS07, WF95]
    • Eigenständig: ./.
    • Vortragende(r): Kagan Soydan
  2. Zentralitätsmaße und der Algorithmus von Dijkstra (SNA) [WF95, JKL+04, CLRS01, BE05]
    • Eigenständig: Erstellen einer Animation
    • Vortragende(r): Dominic Wirkner
  3. Zentralitätsberechnungen mithilfe der Algorithmen von Floyd-Warshall und Brandes (SNA) [Bra01, JKL+04, CLRS01]
    • Eigenständig: Arbeitsweise der Algorithmen veranschaulichen
    • Vortragende(r): Felix Gonsior
  4. All Pairs Shortest Paths mit Algorithmus von Chan (SNA) [AHU74, Cha05]
    • Eigenständig: ./.
    • (Dieser Vortrag ist ersatzlos gestrichen.)
  5. Konstruktion von t-Spannern mithilfe von Theta-Graphen (GN) [Cla87, NS07]
    • Eigenständig: Erstellen einer Animation
    • Vortragende(r): Philipp Gerloff
  6. Spanner-Graphen als Anwendung der Well-Separated Pair Decomposition (GN) [CK95, NS07]
    • Eigenständig: ./.
    • Vortragende(r): Noel-Pascal Baser
  7. Approximation der Dilatation eines euklidischen Graphen (GN) [CK95, NS07]
    • Eigenständig: Erstellen von Beispielen für den Begriff der Dilatation
    • Vortragende(r): Wladimir Penner
  8. Flüsse in Netzwerken (SNA) [OW02]
    • Eigenständig: Präsentationen von Animationen
    • Vortragende(r): Dominik Wolff
  9. Matchings und der Minimum-Cut -Algorithmus von Stoer-Wagner (SNA) [SW94, CLRS01, KT04]
    • Eigenständig: ./.
    • (Dieser Vortrag ist ersatzlos gestrichen.)
  10. Strukturelle Äquivalenz und Blockmodellanalyse (SNA) [WF95, NS04, Ler04]
    • Eigenständig: ./.
    • (Dieser Vortrag ist ersatzlos gestrichen.)
  11. Finden der besten Abkürzung in einem geometrischen Netzwerk (GN) [FGG05]
    • Eigenständig: Veranschaulichung durch eigene Beispiele
    • Vortragende(r): Christian Hammerl
  12. Approximation eines minimalen Manhattan-Netzwerks (GN) [GLN01]
    • Eigenständig: ./.
    • (Dieser Vortrag ist ersatzlos gestrichen)
  13. Spanner-Graphen als Anwendung der Well-Separated Pair Decomposition (GN) [CK95, NS07]
    • Eigenständig: ./.
    • Vortragende(r): Noel-Pascal Baser
  14. Ausdünnung dichter Spanner-Graphen (GN) [GNS05]
    • Eigenständig: ./.
    • (Dieser Vortrag ist ersatzlos gestrichen)
  15. Geometrische Spanner für Routingverfahren in mobilen Netzwerken (GN) [GGH+01]
    • Eigenständig: Erstellen einer Animation
    • Vortragende(r): Arthur Pyka

 


Vorgehensweise

  • Jedes Thema hat eine reproduzierend-darstellende und eine eigenständige Komponente, d.h., es muss nicht nur eine Originalarbeit zusammenfassend dargestellt werden sondern auch, z.B. durch Bearbeiten von Übungsaufgaben, eine eigenständige Leistung erbracht werden. In Absprache mit dem Dozenten können die eigenständigen Komponenten durch eigene Vorschläge ergänzt bzw. ersetzt werden.
  • Zur erfolgreichen Teilnahme an dem Proseminar müssen drei Teilleistungen erbracht werden:
    1. Halten eines Seminarvortrags von etwa 60 Minuten Dauer.
    2. Anfertigen einer schriftlichen Ausarbeitung im Umfang von 10-12 Seiten.
    3. Anwesenheit bei allen Vorträgen und aktive Teilnahme an den Diskussionen.
    Eine nicht ausreichende Leistung in einem dieser Teilgebiete verhindert einen erfolgreichen Abschluss der Proseminars.
  • Eine Reihe wichtiger Hinweise wird von der Fachgruppe "Praktische Informatik" (Prof. Kelter) bereit gestellt. Die Beachtung dieser Hinweise ist für eine erfolgreiche Teilnahme an dem Proseminar unabdingbar. Aus gegebenem Anlass sei (leider) verstärkt auf den Punkt 2.2 (Plagiate) hingewiesen.
  • Eine Zusammenstellung weiterer Hinweise (in englischer Sprache) ist hier zu finden.
  • Die Abgabe der schriftlichen Ausarbeitungen erfolgt bis spätestens zum Ende der Vorlesungszeit. Geben Sie Ihre Arbeit bitte sowohl ausgedruckt als auch in Form einer PDF- oder PostScript-Datei ab.

 


Literatur

[WF95] Wasserman, Stanley undKatherine Faust: Social Network Analysis: Methods and Applications. Cambridge University Press, New York, 1995. [ bib ]
[NS07] Narasimhan, Giri undMichiel Smid: Geometric Spanner Networks. Cambridge University Press, 2007. [ bib ]
[Cla87] Clarkson, Kenneth L.: Approximation Algorithms for Shortest Path Motion Planning. In:Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York City, NY, USA, Mai 1987. ACM. [ bib ]
[GGH+01] Gao, Jie, Leonidas J. Guibas, John Hershberger, Li Zhang undAn Zhu: Geometric Spanner for Routing in Mobile Networks. In:Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc, Long Beach, CA, USA, Oktober 2001. ACM. [ bib ]
[GNS05] Gudmundsson, Joachim, Giri Narasimhan undMichiel H. M. Smid: Fast Pruning of Geometric Spanners. In:Diekert, Volker undBruno Durand(Herausgeber): STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, Band3404 der ReiheLecture Notes in Computer Science, Seiten508-520. Springer, 2005. [ bib ]
[BMN+04] Bose, Prosenjit, Anil Maheshwari, Giri Narasimhan, Michiel Smid undNorbert Zeh: Approximating geometric bottleneck shortest paths. Computational Geometry, 29(3):233-249, 2004. [ bib ]
[GLN01] Gudmundsson, Joachim, Christos Levcopoulos undGiri Narasimhan: Approximating a Minimum Manhattan Network. Nord. J. Comput., 8(2):219-232, 2001. [ bib ]
[FGG05] Farshi, Mohammad, Panos Giannopoulos undJoachim Gudmundsson: Finding the best shortcut in a geometric network. In:Proceedings of the 21st ACM Syposium on Computational Geometry, Pisa, Italien, Juni 2005. ACM. [ bib ]
[NS00] Narasimhan, Giri undMichiel H. M. Smid: Approximating the Stretch Factor of Euclidean Graphs. SIAM J. Comput., 30(3):978-989, 2000. [ bib ]
[CK95] Callahan, Paul B. undS. Rao Kosaraju: A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. Journal of the ACM, 42(1):67-90, 1995. [ bib ]
[Bra01] Brandes, Ulrik: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, 25(2):163-177, 2001. [ bib ]
[SW94] Stoer, Mechthild undFrank Wagner: A Simple Min Cut Algorithm. In:Leeuwen, Jan van(Herausgeber): ESA, Band855 der ReiheLecture Notes in Computer Science, Seiten141-147. Springer, 1994. [ bib ]
[CLRS01] Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest undClifford Stein: Introduction to Algorithms, Second Edition. The MIT Press and McGraw-Hill Book Company, 2001. [ bib ]
[AHU74] Aho, Alfred V., John E. Hopcroft undJeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. [ bib ]
[Cha05] Chan, Timothy M.: All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time. In:WADS, Seiten318-324, 2005. [ bib | http ]
[JKL+04] Jacob, Riko, Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters undDagmar Tenfelde-Podehl: Algorithms for Centrality Indices. In:Brandes, Ulrik und Thomas Erlebach [BE05], Seiten62-82. [ bib | http ]
[OW02] Ottmann, Thomas undPeter Widmayer: Algorithmen und Datenstrukturen, 4. Auflage. Spektrum Akademischer Verlag, Heidelberg, 2002. [ bib ]
[KT04] Kammer, Frank undHanjo Täubig: Connectivity. In:Brandes, Ulrik und Thomas Erlebach [BE05], Seiten143-177. [ bib | http ]
[NS04] Nunkesser, Marc undDaniel Sawitzki: Blockmodels. In:Brandes, Ulrik und Thomas Erlebach [BE05], Seiten253-292. [ bib ]
[BE05] Brandes, Ulrik undThomas Erlebach(Herausgeber): Network Analysis: Methodological Foundations, Band3418 der ReiheLecture Notes in Computer Science. Springer, 2005. [ bib ]
[Ler04] Lerner, Jürgen: Role Assignments. In:Brandes, Ulrik und Thomas Erlebach [BE05], Seiten216-252. [ bib | http ]

 

 
Sitemap Impressum
<www  ls11.cs.uni-dortmund.de>
Die Universität übernimmt keine Haftung für den Inhalt verlinkter externer Internetseiten