Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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, 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.

Questions and Answers

You need to be logged in to be able to post here.