Streaming and communication complexity of clique approximation
DOI10.1007/978-3-642-31594-7_38zbMATH Open1272.68333OpenAlexW101298592MaRDI QIDQ2843271FDOQ2843271
Authors: Magnús M. Halldórsson, Xiaoming Sun, Chengu Wang, Mario Szegedy 
Publication date: 12 August 2013
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_38
Recommendations
- \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- Streaming Lower Bounds for Approximating MAX-CUT
- scientific article; zbMATH DE number 7204504
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (9)
- Optimal lower bounds for matching and vertex cover in dynamic graph streams
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- Independent sets in vertex-arrival streams
- Communication and Streaming Complexity of Approximate Pattern Matching
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
- Streaming algorithms for independent sets in sparse hypergraphs
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
This page was built for publication: Streaming and communication complexity of clique approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843271)
