Unbalanced graph partitioning

DOI10.1007/s00224-012-9436-xzbMath1286.68239OpenAlexW1987654606MaRDI QIDQ372961

Peng Zhang, Ang Sheng Li

Publication date: 21 October 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9436-x

zbMATH Keywords

social networksapproximation algorithmssparsest cutnetwork communityunbalanced cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Cut problems in graphs with a budget constraint
• Multicriteria global minimum cuts
• Unbalanced Graph Partitioning
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Euclidean distortion and the sparsest cut
• Community structure in social and biological networks
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms – ESA 2005
• Expander flows, geometric embeddings and graph partitioning