Praktikum: Graphgeneratoren

• Betreuung: Dr. Michael Baur, Prof. Dr. Dorothea Wagner,Thomas Willhalm
• Vorbesprechung: Donnerstag, 21.10.2004, 15:45 Uhr in SR 301 (im Informatik Hauptgebäude)
• Anmeldung: im Sekretariat (Raum 321), die Teilnehmerzahl ist auf 12 begrenzt

Graphgeneratoren sind Algorithmen zur Erzeugung von Zufallsgraphen, die durch bestimmte Parameter beinflussbar sind. Ein sehr einfacher und klassischer Graphgenerator führt für jedes Knotenpaar ein Zufallsexperiment aus und fügt zwischen diesen eine Kante ein, wenn ein fester Schwellenwert überschritten wird. In den letzten Jahren wurden unzählige weitere Graphgeneratoren für verschiedene Anwendungsszenarien entwickelt.

Eine wichtige Anwendung ist die experimentelle Evaluierung bei der Entwicklung von Graphenalgorithmen. Um Ergebnisse zu erhalten die möglichst nahe an der Realität sind, werden dabei bevorzugt Daten aus realen Anwendungen verwendet. Graphgeneratoren können hierbei einerseits verwendet werden, um die Wirklichkeit möglichst gut nachzubilden, wenn zu wenige oder keine realen Daten verfügbar sind, oder um sehr spezielle Graphen zu erzeugen, die beispielsweise als sehr schwer zu behandeln erkannt wurden.

Eine andere Anwendung ist die Simulation zukünftiger Entwicklungsstadien wachsender Graphen. Dabei sind bestimmte Eigenschaften des Graphen bekannt (z.B. Gradfolge, Kernzahlfolge, …) und es werden Graphgeneratoren gesucht, die Graphen mit diesen Eigenschaften erzeugen.

• Planare Graphen
  • The Random Planar Graphs
  • Generating Labeled Planar Graphs Uniformly at Random
  • Decomposing, Counting, and Generating Unlabeled Cubic Planar Graphs
• AS-Graphen
  • AS-Graph-Generator Inet Topology Generator
  • Einführung der Core-Hierarchie durch Batagelj und Zaversnik: Generalized Cores
  • Vergleich AS-Graph und Inet (Kapitel 4): Drawing the AS Graph
• Zufallsmodelle GNP und GNM
• Preferential Attachment
• Straßengraphen
  • Routing of Multipoint Connection