Sketching Cuts in Graphs and Hypergraphs
From MaRDI portal
Publication:2989051
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
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
