Graphpartitionierung
Ein Graph ist eine Menge von Knoten und Kanten zwischen diesen Knoten. Man unterscheidet zwischen gerichteten Graphen, wo Einbahnstra\xdfen darstellbar sind, oder den ungerichteten Graphen, wo Beziehungen zwischen zwei Knoten immer beidseitig sind. Beispiele sind die graphische Darstellung von Beziehungen in einem sozialen Netz oder Stra\xdfennetze, f\xfcr deren Verarbeitung das Forschungsgebiet von Christian Schulz immer bedeutender wird, wie wir in seinem Gespr\xe4ch mit Gudrun Th\xe4ter erfahren. Eine wichtige Aufgabe im Umgang mit Graphen ist die Aufteilung (oder fachsprachlich Partitionierung), von Graphen in kleinere Teile. Dies kommt z.B. der Parallelisierung der Arbeit auf den Graphen zugute, und ist unumg\xe4nglich, wenn Graphen eine Gr\xf6\xdfe haben, die nicht mehr von einem Prozessor bearbeitet werden kann. Ein wichtiges Merkmal ist hier, die Aufteilung m\xf6glichst gleichm\xe4\xdfig vorzunehmen, damit die Aufteilung von z.B. Rechenzeit gleichm\xe4\xdfig erfolgt, und gleichzeitig wenig Kommunikation zwischen der Bearbeitung der Einzelteile erforderlich ist. Es geht um eine m\xf6glichst gute Skalierbarkeit der Graphverarbeitung. Ein wichtiges Anwendungsproblem ist die Routenplanung, bei der zwischen zwei Punkten auf der Erde die zeitlich k\xfcrzeste Verbindung berechnet werden soll. In der Informatik ist der Dijkstra-Algorithmus der passende Basis-Algorithmus f\xfcr diese Aufgabe, doch er ist f\xfcr gro\xdfe Graphen in seiner urspr\xfcnglichen Form sehr ineffizient. In Kombination mit einer passenden Graphpartitionierung und Algorithmen kann man das Verfahren deutlich effizienter ausf\xfchren und beschleunigen. Ein klassisches Verfahren zur Aufteilung ist das Mehrschichtverfahren \xfcber die Laplace-Matrix, wo ausgenutzt wird, dass zwischen den Eigenwerten der Matrix und der Schnittstruktur des Graphen enge Zusammenh\xe4nge bestehen. Dieses Verfahren wurde zum Mehrschichtverfahren f\xfcr Graphen weiterentwickelt, bei dem in einer sogenannten Kontraktion benachbarte Knoten und parallele Kanten jeweils zusammengef\xfchrt werden, und der Graph zu einem kleinen und kantengewichteten Graph vereinfacht wird. Schlie\xdflich wird das Problem auf einem vereinfachten, groben Gitter gel\xf6st, und dann jeweils mit lokalen Suchen auf feinere Graphen erweitert. F\xfcr die Kontraktion werden Heuristiken und Kantenbewertungsfunktionen verwendet. Ein weiterer Ansatz sind auch evolution\xe4re Algorithmen. Dabei wurde eine allgemeinere Umgebung geschaffen, die auf eine weite Klasse von Optimierungsproblemen angewendet werden kann. Die Graphentheorie ist nat\xfcrlich auch Teil der diskreten Mathematik, und besonders ber\xfchmt ist auch das Traveling Salesperson Problem. Gleichzeitig ist das Thema aber auch in der Theoretischen Informatik, im Algorithm Engineering und in der Software-Entwicklung beheimatet.