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

Gomory-Hu treesgraph partitioningsymmetric submodular functionsuncrossing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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) Programming involving graphs or networks (90C35)

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)