Unbalanced graph partitioning

DOI10.1007/S00224-012-9436-XMaRDI QIDQ372961zbMATH OpenOpenAlexFDO

Authors Peng Zhang, Angsheng 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)

Recommendations

• Unbalanced graph partitioning
• Unbalanced graph cuts with minimum capacity
• Approximation algorithm for sparsest \(k\)-partitioning
• Balanced graph partitioning
• Balanced partitions of trees and applications

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Algorithms – ESA 2005
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Community structure in social and biological networks
• Cut problems in graphs with a budget constraint
• Euclidean distortion and the sparsest cut (extended abstract)
• Expander flows, geometric embeddings and graph partitioning
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Multicriteria global minimum cuts
• Some simplified NP-complete graph problems
• Unbalanced graph partitioning

Cited in

(7)

• Approximation algorithm for sparsest \(k\)-partitioning
• Minimum nonuniform graph partitioning with unrelated weights
• Approximation algorithms for the weighted t-uniform sparsest cut and some other graph partitioning problems
• Unbalanced graph partitioning
• A new approximation algorithm for the unbalanced min s-t cut problem
• A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem
• Algorithms – ESA 2005

This page was built for publication: Unbalanced graph partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372961)