Graphpartitionierung

Viele wichtige Anwendungen in der Informatik verarbeiten große Graphen. Das Ziel der Graphpartitionierung ist es, einen gegebenen Graph G in k möglichst gleichgroße Blöcke zu unterteilen, so dass wenig Kanten zwischen den Blöcken verlaufen. Wichtige Anwendungen der Graphpartitionierung sind unter anderem wissenschaftliches Rechnen auf Großrechnern (Lastbalancierung und Minimierung von Kommunikation), die Analyse von Sozialen Netzwerken oder die Beschleunigung von Routenberechnen auf Straßengraphen.  

Dieses Problem ist NP-vollständig, daher werden wir nicht von Ihnen fordern das Problem exakt zu lösen. In der Praxis haben sich verschiedene Heuristiken, die meistens auf der Multileveltechnik basieren, durchgesetzt.  Bei der Multileveltechnik wird eine Sequenz von kleineren Graphen erzeugt, die die Struktur des ursprünglichen Graphen reflektieren sollen. Sobald der Graph klein genug ist wird er initial partitioniert und die gefunden Partition wird durch die Level nach oben projeziert. Dabei werden in der Regel lokale Verbesserungsoperationen wie z.B. der FM-Algorithmus verwendet, um die gegebene Partitionen auf jedem Level zu verbessern.

Thema der Bachelor- / Masterarbeit
 
Eine Herausforderung dieser Technik ist es den Graph initial mit einer teuren Operation zu partitionieren. Deswegen sollen im Rahmen dieser Arbeit verschiedene Heuristiken entwickelt und untersucht werden, um die Qualtiät (Kantenschnitt) und die Laufzeit dieses Teilschrittes zu verbessern.
 
Vorraussetzungen

• Interesse und solide Kenntnisse uber Algorithmen und Datenstrukturen
• Gute Programmierkentnisse in C++
   

Gebotenes

• Kennenlernen modernster Algorithmen der Graphpartitionierung
• Die Arbeit an einem sehr spannenden Thema

Das hier aufgeführte Thema ist nur ein Beispiel für eine offene Fragestellung. Es gibt (fast) immer weitere interessante Fragestellungen. Interessierte Studenten melden sich bitte bei Christian Schulz.