Praktikum: Algorithmen zur Zerlegung und Clusterung von Graphen

• Betreuung: Marco Gaertler, Martin Holzer, Prof. Dr. Dorothea Wagner
• Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt. Der Kurs kommt ab einer Mindestzahl von vier Teilnehmern zustande.
  Die Anmeldung ist abgeschlossen.

• Folien der Vorbesprechung
• 1. Übungsblatt: Planaren Seperator, Prioritätsclustern
• 2. Übungsblatt: Prioritätsclustern
• 3. Übungsblatt: Prioritätsclustern

Beim Zerlegen bzw. Clustern von Graphen handelt es sich grob um eine Einteilung der Knoten und Kanten des Graphen in Gruppen, die bestimmten Bedingungen oder Kriterien entsprechen soll. Beispiele hierfür sind einerseits die Separation eines Graphen in möglichst gleichgroße Komponenten durch Wegnahme einer möglichst kleinen Knotenmenge und anderseits das Aufteilen der Knotenmenge eines Graphen in Cluster, deren Knoten jeweils intern vergleichsweise stark miteinander, zu Knoten anderer Cluster hingegen eher schwach verbunden sind.

In diesem Programmierpraktikum sollen verschiedene Clusterungs- und Zerlegungsalgorithmen in Java implementiert und ggf. modifiziert bzw. verbessert werden. Die Implementationen sollen dann auf verschiedenen Datensätzen ausgiebig getestet werden.

Nach ein paar gemeinsamen Terminen mit einführendem Charakter und einigen Aufwärmaufgaben wird in Teams von etwa drei Personen jeweils eine größere Programmieraufgabe bearbeitet; Ziel ist eine effiziente und 'schöne' Implementierung in Java sowie eine anschließende experimentelle Evaluation. Jeweils etwa zu Semesterhalbzeit und -ende wird jede Gruppe in einer kurzen Präsentation ihre bisherige Arbeit vorstellen; außerdem ist abschließend eine schriftliche Ausarbeitung in LaTeX zu erstellen.