Streaming and communication complexity of clique approximation

DOI10.1007/978-3-642-31594-7_38MaRDI QIDQ2843271zbMATH OpenOpenAlexFDO

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

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

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

Cited in

(9)

• 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
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Streaming algorithms for independent sets in sparse hypergraphs
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

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)