Approximating minimum cut with bounded size

DOI10.1007/978-3-642-21527-8_26MaRDI QIDQ3091504zbMATH OpenOpenAlexFDO

Authors Giulia Galbiati

Publication date 9 September 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21527-8_26

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms – ESA 2005
• On cutting a few vertices from a graph
• Unbalanced graph cuts with minimum capacity
• Approximating Maximum Cut with Limited Unbalance
• On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems

Cited in

(11)

• Bounded size graph clustering with applications to stream processing
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Approximating the minimum bisection size (extended abstract)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• Algorithms – ESA 2005
• Minimum cuts in near-linear time
• Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée
• Computational experience with a SDP-based algorithm for maximum cut with limited unbalance
• On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems
• Theoretical lower bound for border length minimization problem
• Approximation algorithms for minimum \(K\)-cut

This page was built for publication: Approximating minimum cut with bounded size

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