Sketching Cuts in Graphs and Hypergraphs

DOI10.1145/2688073.2688093zbMath1365.68469arXiv1409.2391OpenAlexW1978676170MaRDI QIDQ2989051

Robert Krauthgamer, Dmitry Kogan

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.2391

zbMATH Keywords

sketchinghypergraphsstreamingMax-cutsparsifiers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

Minimum Cuts and Sparsification in Hypergraphs ⋮ Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Sparsification of Binary CSPs ⋮ Unnamed Item ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. ⋮ Unnamed Item ⋮ Sparsification of Binary CSPs ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems

This page was built for publication: Sketching Cuts in Graphs and Hypergraphs