Streaming and Communication Complexity of Clique Approximation

DOI10.1007/978-3-642-31594-7_38zbMath1272.68333OpenAlexW101298592MaRDI QIDQ2843271

Xiaoming Sun, Magnús M. Halldórsson, Chengu Wang

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

zbMATH Keywords

independent setcommunication complexitystreamingclique approximation

Mathematics Subject Classification ID

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 (5)

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

This page was built for publication: Streaming and Communication Complexity of Clique Approximation