Daniel Delling, Andrew GOldberg, Ilya Razenshteyn, Renato F. Weneck
Abstract. We present a novel approach to graph partitioning based on the notion of natural
cuts. Our algorithm, called PUNCH, has two phases. The rst phase performs a
series of minimum-cut computations to identify and contract dense regions of the
graph. This reduces the graph size signi cantly, but preserves its general structure.
The second phase uses a combination of greedy and local search heuristics to assemble
the nal partition. The algorithm performs especially well on road networks, which
have an abundance of natural cuts (such as bridges, mountain passes, and ferries).
In a few minutes, it obtains the best known partitions for continental-sized networks,
signi cantly improving on previous results.
No comments:
Post a Comment