Institut für Theoretische Informatik, Algorithmik

Praktikum: Algorithmen zur Zerlegung und Clusterung von Graphen

Allgemeines

Aktuelles

Ausarbeitungen

Gruppe Thema Ausarbeitung
Hilal Akbaba und Stefan Hartte Planar-Separator-Theorem Ausarbeitung
Daniel Karch und Hanno Kersting Prioritätsclustern Ausarbeitung

Übungen

Inhalt

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.

Ablauf

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.