Bounded size graph clustering with applications to stream processing

DOI10.4230/LIPICS.FSTTCS.2009.2325MaRDI QIDQ2920135zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman, Joel Wolf

Publication date 24 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_c5e9.html

zbMATH Keywords

graph partitioninguncrossingsymmetric submodular functionsGomory-Hu trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Approximating minimum cut with bounded size
• Cut problems in graphs with a budget constraint
• Cut Problems in Graphs with a Budget Constraint
• Graph clustering with a constraint on cluster sizes
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited in

(1)

• Correlation clustering with constrained cluster sizes and extended weights bounds

This page was built for publication: Bounded size graph clustering with applications to stream processing

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