Approximating minimum cut with bounded size

DOI10.1007/978-3-642-21527-8_26zbMATH Open1344.68175OpenAlexW47413040MaRDI QIDQ3091504FDOQ3091504

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

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

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)

Cited In (11)

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

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)