Unbalanced graph cuts with minimum capacity

DOI10.1007/S11704-014-3289-1MaRDI QIDQ2515430zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmcombinatorial optimizationmin cutsocial networkunbalanced cut

Mathematics Subject Classification ID

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

Recommendations

• Algorithms – ESA 2005
• Approximating Maximum Cut with Limited Unbalance
• Approximation algorithms for maximum cut with limited unbalance
• From Graph Orientation to the Unweighted Maximum Cut
• Approximation algorithms for MAX RES CUT with limited unbalanced constraints
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Balanced cut approximation in random geometric graphs
• Balanced Cut Approximation in Random Geometric Graphs
• Approximating graph-constrained max-cut
• Minimal graph cuts on network subgraphs

Cites work

• A new approach to the minimum cut problem
• A Polylogarithmic Approximation of the Minimum Bisection
• A tight bound on approximating arbitrary metrics by tree metrics
• Algorithms – ESA 2005
• Approximation algorithms and hardness of the \(k\)-route cut problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Computing All Small Cuts in an Undirected Network
• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• Multicriteria global minimum cuts
• On cutting a few vertices from a graph
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Some simplified NP-complete graph problems
• Unbalanced graph partitioning

Cited in

(8)

• From Graph Orientation to the Unweighted Maximum Cut
• A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem
• Unbalanced graph partitioning
• Approximating minimum cut with bounded size
• Unbalanced graph partitioning
• Algorithms – ESA 2005
• A new approximation algorithm for the unbalanced min s-t cut problem
• Most balanced minimum cuts

This page was built for publication: Unbalanced graph cuts with minimum capacity

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