Fetching the paper…
Reading the bibliography…
We survey recent trends in practical algorithms for balanced graph partitioning together with applications and future research directions.
An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators
C. Lanczos · 1950
Earlier work this paper cites.
Maximal Flow through a Network
L. R. Ford and D. R. Fulkerson · 1956
Earlier work this paper cites.
An Automatic Method of Solving Discrete Programming Problems
A. H. Land and A. G. Doig · 1960
Earlier work this paper cites.
An Efficient Heuristic Procedure for Partitioning Graphs
B. W. Kernighan and S. Lin · 1970
Earlier work this paper cites.
Algorithms for Partitioning of Graphs and Computer Logic Based on Eigenvectors of Connection Matrices
W. E. Donath and A. J. Hoffman · 1972
Earlier work this paper cites.
Lower Bounds for the Partitioning of Graphs
W. E. Donath and A. J. Hoffman · 1973
Earlier work this paper cites.
Graph Partitioning and Constructing Optimal Decision Trees are Polynomial Complete Problems
L. Hyafil and R. Rivest · 1973
Earlier work this paper cites.
Some Simplified NP-Complete Problems
M. R. Garey, D. S. Johnson, and L. Stockmeyer · 1974
Earlier work this paper cites.
A Property of Eigenvectors of Nonnegative Symmetric Matrices and its Application to Graph Theory
M. Fiedler · 1975
Earlier work this paper cites.
Computers and Intractability: A Guide to the Theory of NP-Completeness
M. R. Garey and D. S. Johnson · 1979
Earlier work this paper cites.
Computer Solution of Large Sparse Positive Definite Systems
A. George and J. W. H. Liu · 1981
Earlier work this paper cites.
A Linear-Time Heuristic for Improving Network Partitions
C. M. Fiduccia and R. M. Mattheyses · 1982
Earlier work this paper cites.
Least Squares Quantization in PCM
S. Lloyd · 1982
Earlier work this paper cites.
Graph Bisection Algorithms with Good Average Case Behavior
T. Bui, S. Chaudhuri, F. Leighton, and M. Sipser · 1987
Earlier work this paper cites.
Eigenvalues and Graph Bisection: An Average-Case Analysis)
R. B. Boppana · 1987
Earlier work this paper cites.
Tabu Search — Part I
F. Glover · 1989
Earlier work this paper cites.
Multiple-Way Network Partitioning
L. A. Sanchis · 1989
Earlier work this paper cites.
Tabu Search — Part II
F. Glover · 1990
Earlier work this paper cites.
Partitioning Sparse Matrices with Eigenvectors of Graphs
A. Pothen, H. D. Simon, and K. P. Liou · 1990
Earlier work this paper cites.
The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems)
J. Hromkovič and B. Monien · 1991
Earlier work this paper cites.
The Complexity of Congestion-1 Embedding in a Hypercube
Y. M. Kim and T.-H. Lai · 1991
Earlier work this paper cites.
A Unified Geometric Approach to Graph Separators
G. Miller, S.-H. Teng, and S. Vavasis · 1991
Earlier work this paper cites.
Partitioning of Unstructured Problems for Parallel Processing
H. D. Simon · 1991
Earlier work this paper cites.
Performance of Dynamic Load Balancing Algorithms for Unstructured Mesh Calculations
R. D. Williams · 1991
Earlier work this paper cites.
Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
F. T. Leighton · 1992
Earlier work this paper cites.
A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems
S. T. Barnard and H. D. Simon · 1993
Earlier work this paper cites.
New Faster Kernighan-Lin-type Graph-Partitioning Algorithms
S. Dutt · 1993
Earlier work this paper cites.
Automatic Partitioning of Unstructured Meshes for the Parallel Solution of Problems in Computational Mechanics
C. Farhat and M. Lesoinne · 1993
Earlier work this paper cites.
Random Walks on Graphs: A Survey
L. Lovász · 1993
Earlier work this paper cites.
Between Min Cut and Graph Bisection
D. Wagner and F. Wagner · 1993
Earlier work this paper cites.
A Polynomial Algorithm for the k k -Cut Problem for Fixed k k
O. Goldschmidt and D. S. Hochbaum · 1994
Earlier work this paper cites.
Partitioning with Space-filling Curves
J. R. Pilkington and S. B. Baden · 1994
Earlier work this paper cites.
Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs
F. Pellegrini · 1994
Earlier work this paper cites.
Using Helpful Sets to Improve Graph Bisections
R. Diekmann, B. Monien, and R. Preis · 1995
Earlier work this paper cites.
A Multilevel Algorithm for Partitioning Graphs
B. Hendrickson and R. Leland · 1995
Earlier work this paper cites.
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
B. Hendrickson and R. Leland · 1995
Earlier work this paper cites.
A Localized Algorithm for Optimizing Unstructured Mesh Partitions
C. Walshaw, M. Cross, and M. G. Everett · 1995
Earlier work this paper cites.
Enhancing Data Locality by Using Terminal Propagation
B. Hendrickson, R. Leland, and R. V. Driessche · 1996
Earlier work this paper cites.
Parallel Multilevel k k -way Partitioning Scheme for Irregular Graphs
G. Karypis and V. Kumar · 1996
Earlier work this paper cites.
Tabu Search for Graph Partitioning
E. Rolland, H. Pirkul, and F. Glover · 1996
Earlier work this paper cites.
A Branch-and-Cut Algorithm for the Equicut Problem
L. Brunetta, M. Conforti, and G. Rinaldi · 1997
Earlier work this paper cites.
Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes
K. Schloegel, G. Karypis, and V. Kumar · 1997
Earlier work this paper cites.
How Good is Recursive Bisection?
H. D. Simon and S. H. Teng · 1997
Earlier work this paper cites.
Dynamic load-balancing for parallel adaptive unstructured meshes
C. Walshaw, M. Cross, and M. G. Everett · 1997
Earlier work this paper cites.
The Node Capacitated Graph Partitioning Problem: A Computational Study
C. E. Ferreira, A. Martin, C. C. De Souza, R. Weismantel, and L. A. Wolsey · 1998
Earlier work this paper cites.
Geometric Mesh Partitioning: Implementation and Experiments
J. R. Gilbert, G. L. Miller, and S. H. Teng · 1998
Earlier work this paper cites.
Graph Partitioning and Parallel Solvers: Has the Emperor No Clothes?
B. Hendrickson · 1998
Earlier work this paper cites.
The Metropolis Algorithm for Graph Bisection
M. Jerrum and G. B. Sorkin · 1998
Earlier work this paper cites.
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
G. Karypis and V. Kumar · 1998
Earlier work this paper cites.
Multilevel k k -way Partitioning Scheme for Irregular Graphs
G. Karypis and V. Kumar · 1998
Earlier work this paper cites.
Fast Approximate Graph Partitioning Algorithms
G. Even, J. S. Naor, S. Rao, and B. Schieber · 1999
Earlier work this paper cites.
Graph Partitioning and Continuous Quadratic Programming
W. W. Hager and Y. Krylyuk · 1999
Earlier work this paper cites.
Multilevel k k -Way Hypergraph Partitioning
G. Karypis and V. Kumar · 1999
Earlier work this paper cites.
Parallel Multilevel series k k -Way Partitioning Scheme for Irregular Graphs
G. Karypis and V. Kumar · 1999
Earlier work this paper cites.
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs
R. Preis · 1999
Earlier work this paper cites.
Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM
R. Diekmann, R. Preis, F. Schlimbach, and C. Walshaw · 2000
Earlier work this paper cites.
Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM
R. Diekmann, R. Preis, F. Schlimbach, and C. Walshaw · 2000
Earlier work this paper cites.
Graph Partitioning Models for Parallel Computing
B. Hendrickson and T. G. Kolda · 2000
Earlier work this paper cites.
Solving Graph Bisection Problems with Semidefinite Programming
S. E. Karisch, F. Rendl, and J. Clausen · 2000
Earlier work this paper cites.
A Unified Algorithm for Load-Balancing Adaptive Scientific Simulations
K. Schloegel, G. Karypis, and V. Kumar · 2000
Earlier work this paper cites.
A Hierarchical Partition Model for Adaptive Finite Element Computation
J. Teresco, M. Beall, J. Flaherty, and M. Shephard · 2000
Earlier work this paper cites.
Fennel: Streaming Graph Partitioning for Massive Scale Graphs
C. E. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic · 2000
Earlier work this paper cites.
Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm
C. Walshaw and M. Cross · 2000
Earlier work this paper cites.
A Hypergraph-Partitioning Approach for Coarse-Grain Decomposition
U. Catalyurek and C. Aykanat · 2001
Earlier work this paper cites.
Lower Bounds and Exact Algorithms for the Graph Partitioning Problem Using Multicommodity Flows
N. Sensen · 2001
Earlier work this paper cites.
Multilevel Mesh Partitioning for Heterogeneous Communication Networks
C. Walshaw and M. Cross · 2001
Earlier work this paper cites.
A Polylogarithmic Approximation of the Minimum Bisection
U. Feige and R. Krauthgamer · 2002
Earlier work this paper cites.
On the Quality of Partitions based on Space-Filling Curves
J. Hungershöfer and J.-M. Wierum · 2002
Earlier work this paper cites.
Parallel Static and Dynamic Multi-Constraint Graph Partitioning
K. Schloegel, G. Karypis, and V. Kumar · 2002
Earlier work this paper cites.
Using Multi-Level Graphs for Timetable Information
F. Schulz, D. Wagner, and C. D. Zaroliagis · 2002
Earlier work this paper cites.
Parallel mesh partitioning on distributed memory systems
C. Walshaw and M. Cross · 2002
Earlier work this paper cites.
Multilevel Optimization in VLSICAD
J. Cong and J. Shinnerl · 2003
Cited alongside, same era.
A Simple Approximation Algorithm for the Weighted Matching Problem
D. Drake and S. Hougardy · 2003
Cited alongside, same era.
Graph Partitioning using Linear and Semidefinite Programming
A. Lisser and F. Rendl · 2003
Cited alongside, same era.
Graph Partitioning for High-Performance Scientific Simulations
K. Schloegel, G. Karypis, and V. Kumar · 2003
Cited alongside, same era.
Multicommodity Flow Approximation used for Exact Graph Partitioning
M. Sellmann, N. Sensen, and L. Timajev · 2003
Cited alongside, same era.
Parallel Multilevel Methods: Adaptive Mesh Refinement and Loadbalancing
G. Zumbusch · 2003
Cited alongside, same era.
Pregel: a System for Large-Scale Graph Processing
G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski · 2010
Later among the works it cites.
Biomat 2009: International Symposium on Mathematical and Computational Biology, Brasilia, Brazil, 1-6 August 2009
R. Mondaini · 2010
Later among the works it cites.
Networks: An Introduction
M. Newman · 2010
Later among the works it cites.
n n -Level Graph Partitioning
V. Osipov and P. Sanders · 2010
Later among the works it cites.
A Fast Multigrid Algorithm for Energy Minimization under Planar Density Constraints
D. Ron, I. Safro, and A. Brandt · 2010
Later among the works it cites.
Variable partition inertia: Graph repartitioning and load balancing for adaptive meshes
C. Walshaw · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Expander Flows, Geometric Embeddings and Graph Partitioning
S. Arora, S. Rao, and U. Vazirani · 2004
Cited alongside, same era.
MapReduce: Simplified Data Processing on Large Clusters
J. Dean and S. Ghemawat · 2004
Cited alongside, same era.
Solving the Mesh-Partitioning Problem with an Ant-Colony Algorithm
P. Korosec, J. Silc, and B. Robic · 2004
Cited alongside, same era.
An Extremely Fast, Exact Algorithm for Finding Shortest Paths in Static Networks with Geographical Background
U. Lauther · 2004
Cited alongside, same era.
A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts
K. Lang and S. Rao · 2004
Cited alongside, same era.
Graph Partitioning with the Party Library: Helpful-Sets in Practice
B. Monien and S. Schamberger · 2004
Cited alongside, same era.
Controlling Unstructured Mesh Partitions for Massively Parallel Simulations
M. Zhou, O. Sahni, et al · 2010
Later among the works it cites.
The Combinatorial BLAS: Design, Implementation, and Applications
A. Buluç and J. R. Gilbert · 2011
Later among the works it cites.
A Multilevel Memetic Approach for Improving Graph k k -Partitions
U. Benlic and J. K. Hao · 2011
Later among the works it cites.
An Effective Multilevel Tabu Search Approach for Balanced Graph Partitioning
U. Benlic and J. K. Hao · 2011
Later among the works it cites.
Avoiding Hot-Spots on Two-Level Direct Networks
A. Bhatele, N. Jain, W. D. Gropp, and L. V. Kale · 2011
Later among the works it cites.
Heuristic-Based Techniques for Mapping Irregular Communication Graphs to Mesh Topologies
A. Bhatele and L. Kale · 2011
Later among the works it cites.
Graph Partitioning
C. Bichot and P. Siarry, editors · 2011
Later among the works it cites.
PaToH: Partitioning Tool for Hypergraphs
Ü. Çatalyürek and C. Aykanat · 2011
Later among the works it cites.
Triangle Listing in Massive Networks and its Applications
S. Chu and J. Cheng · 2011
Later among the works it cites.
Algebraic Distance on Graphs
J. Chen and I. Safro · 2011
Later among the works it cites.
Graph Partitioning with Natural Cuts
D. Delling, A. V. Goldberg, et al · 2011
Later among the works it cites.
Customizable Route Planning
D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck · 2011
Later among the works it cites.
Scaling Algorithms for Approximate and Exact Maximum Weight Matching
R. Duan, S. Pettie, and H.-H. Su · 2011
Later among the works it cites.
Adaptation au repartitionnement de graphes d’une méthode d’optimisation globale par diffusion
S. Fourestier and F. Pellegrini · 2011
Later among the works it cites.
An O ( n 4 ) O(n^{4}) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
A. Feldmann and P. Widmayer · 2011
Later among the works it cites.
An Efficient Memetic Algorithm for the Graph Partitioning Problem
P. Galinier, Z. Boujbel, and M. C. Fernandes · 2011
Later among the works it cites.
Generic Topology Mapping Strategies for Large-scale Parallel Architectures
T. Hoefler and M. Snir · 2011
Later among the works it cites.
Genetic Approaches for Graph Partitioning: A Survey
J. Kim, I. Hwang, Y.-H. Kim, and B.-R. Moon · 2011
Later among the works it cites.
VLSI Physical Design - From Graph Partitioning to Timing Closure
A. B. Kahng, J. Lienig, I. L. Markov, and J. Hu · 2011
Later among the works it cites.
Static Mapping of Process Graphs
F. Pellegrini · 2011
Later among the works it cites.
Relaxation-Based Coarsening and Multiscale Graph Organization
D. Ron, I. Safro, and A. Brandt · 2011
Later among the works it cites.
Exascale Computing Technology Challenges
J. Shalf, S. Dosanjh, and J. Morrison · 2011
Later among the works it cites.
Parallel Graph Partitioning on Multicore Architectures
X. Sui, D. Nguyen, M. Burtscher, and K. Pingali · 2011
Later among the works it cites.
Engineering Multilevel Graph Partitioning Algorithms
P. Sanders and C. Schulz · 2011
Later among the works it cites.
Multiscale Approach for the Network Compression-Friendly Ordering
I. Safro and B. Temkin · 2011
Later among the works it cites.
A Review on Graph Based Segmentation
K. S. Camilus and V. K. Govindan · 2012
Later among the works it cites.
The Impact of Heterogeneous Multi-Core Clusters on Graph Partitioning: An Empirical Study
S. Y. Chan, T. C. Ling, and E. Aubanel · 2012
Later among the works it cites.
Power System Reconfiguration based on Multi-Level Graph Partitioning
H. J. Diansheng Guo, Ke Liao · 2012
Later among the works it cites.
Exact Combinatorial Branch-and-Bound for Graph Bisection
D. Delling, A. V. Goldberg, I. Razenshteyn, and R. F. Werneck · 2012
Later among the works it cites.
Better Bounds for Graph Bisection
D. Delling and R. F. Werneck · 2012
Later among the works it cites.
Optimized Hybrid Parallel Lattice Boltzmann Fluid Flow Simulations on Complex Geometries
J. Fietz, M. Krause, C. Schulz, P. Sanders, and V. Heuveline · 2012
Later among the works it cites.
A. Gutfraind, L. A. Meyers, and I. Safro · 2012
Later among the works it cites.
Distributed GraphLab: A Framework for Machine Learning in the Cloud
Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein · 2012
Later among the works it cites.
Candidate Sets for Alternative Routes in Road Networks
D. Luxen and D. Schieferdecker · 2012
Later among the works it cites.
Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning
H. Meyerhenke and T. Sauerwald · 2012
Later among the works it cites.
Scotch and PT-Scotch Graph Partitioning Software: An Overview
F. Pellegrini · 2012
Later among the works it cites.
Streaming Graph Partitioning for Large Distributed Graphs
I. Stanton and G. Kliot · 2012
Later among the works it cites.
Distributed Evolutionary Graph Partitioning
P. Sanders and C. Schulz · 2012
Later among the works it cites.
Advanced Coarsening Schemes for Graph Partitioning
I. Safro, P. Sanders, and C. Schulz · 2012
Later among the works it cites.
Space-Filling Curves
M. Bader · 2013
Closest in time.
Rank Reordering for MPI Communication Optimization
B. Brandfass, T. Alrutz, and T. Gerhold · 2013
Closest in time.
Scalable Matrix Computations on Large Scale-Free Graphs Using 2D Graph Partitioning
E. G. Boman, K. D. Devine, and S. Rajamanickam · 2013
Closest in time.
Graph Partitioning and Graph Clustering – 10th DIMACS Impl. Challenge
D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, editors · 2013
Closest in time.
Efficient Parallel and External Matching
M. Birn, V. Osipov, P. Sanders, C. Schulz, and N. Sitchinava · 2013
Closest in time.
Faster Customization of Road Networks
D. Delling and R. F. Werneck · 2013
Closest in time.
An Exact Algorithm for Graph Partitioning
W. W. Hager, D. T. Phan, and H. Zhang · 2013
Closest in time.
Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques
E. Jeannot, G. Mercier, and F. Tessier · 2013
Closest in time.
Scalable Parallel Graph Partitioning
S. Kirmani and P. Raghavan · 2013
Closest in time.
KONECT – the koblenz network collection
J. Kunegis · 2013
Closest in time.
Multi-threaded Graph Partitioning
D. Lasalle and G. Karypis · 2013
Closest in time.
June 2013 | TOP500 supercomputer sites
H. Meuer, E. Strohmaier, H. Simon, and J. Dongarra · 2013
Closest in time.
Community Detection and Graph Partitioning
M. E. J. Newman · 2013
Closest in time.
Restreaming Graph Partitioning: Simple Versatile Algorithms for Advanced Balancing
J. Nishimura and J. Ugander · 2013
Closest in time.
A survey of Graph Theoretical Approaches to Image Segmentation
B. Peng, L. Zhang, and D. Zhang · 2013
Closest in time.
High Quality Graph Partititioning. PhD thesis
C. Schulz · 2013
Closest in time.
Think Locally, Act Globally: Highly Balanced Graph Partitioning
P. Sanders and C. Schulz · 2013
Closest in time.
GPS: A Graph Processing System
S. Salihoglu and J. Widom · 2013
Closest in time.
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
R. van Bevern, A. E. Feldmann, M. Sorge, and O. Suchý · 2013
Closest in time.
Tree-based coarsening and partitioning of complex networks
R. Glantz, H. Meyerhenke, and C. Schulz · 2014
Closest in time.
A multilevel bilinear programming algorithm for the vertex separator problem
W. W. Hager, J. T. Hungerford, and I. Safro · 2014
Closest in time.
Partitioning Complex Networks via Size-constrained Clustering
H. Meyerhenke, P. Sanders, and C. Schulz · 2014
Closest in time.
(Semi-)External Algorithms for Graph Partitioning and Clustering
Y. Akhremtsev, P. Sanders, and C. Schulz · 2015
Closest in time.
Algorithms for mapping parallel processes onto grid and torus architectures
R. Glantz, H. Meyerhenke, and A. Noe · 2015
Closest in time.
Parallel Graph Partitioning for Complex Networks
H. Meyerhenke, P. Sanders, and C. Schulz · 2015
Closest in time.