Advanced Coarsening Schemes for Graph Partitioning

Details Advanced Coarsening Schemes for Graph Partitioning Advanced Coarsening Schemes for Graph Partitioning

2012-01-31

arxiv.org/abs/1201.6488v2

Computer Science

Data Structures and Algorithms

Scientific paper

The graph partitioning problem is widely used and studied in many practical and theoretical applications. The multilevel strategies represent today one of the most effective and efficient generic frameworks for solving this problem on large-scale graphs. Most of the attention in designing the multilevel partitioning frameworks has been on the refinement phase. In this work we focus on the coarsening phase, which is responsible for creating structurally similar to the original but smaller graphs. We compare different matching- and AMG-based coarsening schemes, experiment with the algebraic distance between nodes, and demonstrate computational results on several classes of graphs that emphasize the running time and quality advantages of different coarsenings.

Affiliated with

Also associated with

No associations

Rating

Advanced Coarsening Schemes for Graph Partitioning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Advanced Coarsening Schemes for Graph Partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Advanced Coarsening Schemes for Graph Partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56648