Streaming and Communication Complexity of Clique Approximation
From MaRDI portal
Publication:2843271
DOI10.1007/978-3-642-31594-7_38zbMath1272.68333OpenAlexW101298592MaRDI QIDQ2843271
Xiaoming Sun, Magnús M. Halldórsson, 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)
Related Items
Streaming algorithms for independent sets in sparse hypergraphs, New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory, New bounds for the CLIQUE-GAP problem using graph decomposition theory, Unnamed Item, Optimal lower bounds for matching and vertex cover in dynamic graph streams