New bounds for the CLIQUE-GAP problem using graph decomposition theory

DOI10.1007/S00453-017-0277-5MaRDI QIDQ1709587zbMATH OpenOpenAlexFDO

Authors Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, Lin F. Yang

Publication date 6 April 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0277-5

zbMATH Keywords

streaming algorithmcliquegraph decompositioncommunication complexitytriangle counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Streaming and communication complexity of clique approximation
• Better Gap-Hamming Lower Bounds via Better Round Elimination

Cites work

• scientific article; zbMATH DE number 3841905 (Why is no real title available?)
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• A second look at counting triangles in graph streams
• Approximate counting of cycles in streams
• Compressed sensing
• Computing and Combinatorics
• Estimating Clustering Indexes in Data Streams
• Graph Sparsification in the Semi-streaming Model
• Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24--28, 2015. Proceedings. Part II
• On the Decomposition of Graphs
• Streaming Lower Bounds for Approximating MAX-CUT
• Streaming and communication complexity of clique approximation
• Trading off space for passes in graph streaming problems

Cited in

(6)

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Independent sets in vertex-arrival streams
• Matroid-constrained vertex cover
• Clique Cover and Graph Separation
• On NP-hardness of the clique partition -- independence number gap recognition and related problems
• Streaming and communication complexity of clique approximation

This page was built for publication: New bounds for the CLIQUE-GAP problem using graph decomposition theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709587)