Name
Abstract | ||
|---|---|---|
We present a novel approach to graph partitioning based on the notion of \emph{natural cuts}. Our algorithm, called PUNCH, has two phases. The first 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 final 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, significantly improving on previous results. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/IPDPS.2011.108 | IPDPS |
Keywords | DocType | Citations |
graph partitioning,general structure,novel approach,minimum-cut computation,graph size,natural cuts,local search heuristics,final partition,continental-sized network,natural cut,contract dense region,known partition,greedy algorithms,radiation detector,assembly,graph theory,minimum cut,greedy algorithm,radiation detectors,edge detection,local search | Conference | 51 |
PageRank | References | Authors |
1.84 | 29 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Delling | 1 | 2049 | 108.90 |
| Andrew V. Goldberg | 2 | 5883 | 676.30 |
| Ilya Razenshteyn | 3 | 154 | 8.80 |
| Renato F. Werneck | 4 | 1743 | 84.33 |