Engineering Multilevel Graph Partitioning Algorithms

Details Engineering Multilevel Graph Partitioning Algorithms Engineering Multilevel Graph Partitioning Algorithms

2010-11-30

arxiv.org/abs/1012.0006v3

Computer Science

Data Structures and Algorithms

fixed a problem with the medium sized instances

Scientific paper

We present a multi-level graph partitioning algorithm using novel local improvement algorithms and global search strategies transferred from the multi-grid community. Local improvement algorithms are based max-flow min-cut computations and more localized FM searches. By combining these techniques, we obtain an algorithm that is fast on the one hand and on the other hand is able to improve the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 317 improvements for the tables 1%, 3% and 5% imbalance. Moreover, in 118 additional cases we have been able to reproduce the best cut in this benchmark.

Affiliated with

Also associated with

No associations

Rating

Engineering Multilevel Graph Partitioning Algorithms 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 Engineering Multilevel Graph Partitioning Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Engineering Multilevel Graph Partitioning Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-574025