Beyond good partition shapes: an analysis of diffusive graph partitioning

DOI10.1007/s00453-012-9666-yzbMath1257.05131OpenAlexW1995006434MaRDI QIDQ1934315

Thomas Sauerwald, Henning Meyerhenke

Publication date: 28 January 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9666-y

zbMATH Keywords

random walksdiffusive graph partitioningdisturbed diffusionrelaxed cut optimization

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)

Related Items (max. 100)

FOS/C

Uses Software

• Bubble-FOS/C
• PT-Scotch
• DibaP
• Graclus

Cites Work

• Graph clustering
• Randomized diffusion for indivisible loads
• Balanced graph partitioning
• Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• An Efficient Heuristic Procedure for Partitioning Graphs
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• Least squares quantization in PCM
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Finding sparse cuts locally using evolving sets
• Machine Learning: ECML 2004
• Analyzing Disturbed Diffusion on Networks
• Efficient schemes for nearest neighbor load balancing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Beyond good partition shapes: an analysis of diffusive graph partitioning