pith. sign in

arxiv: 1110.0477 · v1 · pith:EIRGPMABnew · submitted 2011-10-03 · 💻 cs.NE · cs.DC

Distributed Evolutionary Graph Partitioning

Peter Sanders , Christian Schulz This is my paper
classification 💻 cs.NE cs.DC
keywords graphpartitioningabledistributedevolutionaryimprovekaffpaknown
0
0 comments X
read the original abstract

We present a novel distributed evolutionary algorithm, KaFFPaE, to solve the Graph Partitioning Problem, which makes use of KaFFPa (Karlsruhe Fast Flow Partitioner). The use of our multilevel graph partitioner KaFFPa provides new effective crossover and mutation operators. By combining these with a scalable communication protocol we obtain a system that is able to improve the best known partitioning results for many inputs in a very short amount of time. For example, in Walshaw's well known benchmark tables we are able to improve or recompute 76% of entries for the tables with 1%, 3% and 5% imbalance.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Restoring Sparsity in Potts Machines via Mean-Field Constraints

    cond-mat.stat-mech 2026-02 unverdicted novelty 6.0

    Mean-field constraints restore sparsity in Potts machines by replacing dense pairwise constraint couplings with dynamically updated single-node biases, achieving comparable partitioning quality with reduced density an...