Generating Graphs with Guarantees on Partition Costs
F. Merz · 2011
Partitioning a graph is to divide its set of vertices into a fixed number of equally sized disjoint subsets minimizing the number of edges between them. In this work, we describe an algorithm to generate large random graphs such that an optimal solution to this problem is known. For this task, we first generate dense subgraphs such that we know a lower bound on the size of the minimal cut for each of these subgraphs. We then connect the subgraphs by few edges such that the partition induced by these subgraphs is known to be optimal. This algorithm has expected linear run-time. Zusammenfassung Graphpartitionierung ist das Problem, die Knotenmenge eines Graphen in disjunkte, gleich grose Teilmengen aufzuteilen, welche die Anzahl der Kanten zwischen diesen Teilmengen minimiert. In dieser Arbeit beschreiben wir einen Algorithmus, um grose Zufallsgraphen generieren, zu denen wir eine optimale Partitionierung kennen. Um dies zu erreichen, generieren wir zuerst dichte Teilgraphen, fur welche wir die untere Schranke fur die Grose deren minimalen Schnittes kennen. Diese Teilgraphen verbinden wir danach mit einigen wenigen Kanten, so dass die durch die Teilgraphen induzierte Partitionierung optimal ist. Die erwartete Laufzeit dieses Algorithmus ist linear.