Unbalanced graph cuts with minimum capacity

DOI10.1007/s11704-014-3289-1zbMath1336.68205OpenAlexW2142835653MaRDI QIDQ2515430

Peng Zhang

Publication date: 5 August 2015

Published in: Frontiers of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11704-014-3289-1

zbMATH Keywords

combinatorial optimizationapproximation algorithmsocial networkunbalanced cutmin cut

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• On cutting a few vertices from a graph
• Multicriteria global minimum cuts
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Unbalanced Graph Partitioning
• A new approach to the minimum cut problem
• Computing All Small Cuts in an Undirected Network
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Polylogarithmic Approximation of the Minimum Bisection
• Algorithms – ESA 2005
• A tight bound on approximating arbitrary metrics by tree metrics