Gegeben sei ein zusammenhängender Graph G=(V,E). Das Knotenseparatorproblem sucht eine Aufteilung der Knotenmenge V in drei disjunkte Mengen V_1, V_2 und S, so dass die Vereinigung dieser Mengen wieder V ergibt. S heißt dann Knotenseparator, wenn durch das Entfernen der Menge aus V zwei unabhängige Graphen G_1 und G_2 erzeugt werden.

Ziel dieser Arbeit ist es, basierend auf Flusstechniken einen neuen Algorithmus zur Verbesserung eines gegebenen Knotenseparators zu entwerfen und das neue Verfahren mit bestehenden Verfahren empirisch zu vergleichen.

 Mindestens 2 der folgenden 3 Voraussetzungen sollten erfüllt sein.

• gute bis sehr gute Kenntnisse in C++ (in Ausnahmefällen auch Java)
• Spaß an kombinatorischen Problemen und algorithmischen Fragestellungen
• Interesse an Graphpartitionierung

• Einarbeitung in wichtige Techniken der Graphpartitionierung
• Forschung an aktuellen Fragestellungen