New bounds for the CLIQUE-GAP problem using graph decomposition theory
DOI10.1007/S00453-017-0277-5zbMATH Open1391.68048OpenAlexW2577465605MaRDI QIDQ1709587FDOQ1709587
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
Recommendations
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- Streaming and communication complexity of clique approximation
- An optimal lower bound on the communication complexity of gap-Hamming-distance
- Better Gap-Hamming Lower Bounds via Better Round Elimination
- An optimal lower bound on the communication complexity of gap-Hamming-distance
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)
Cites Work
- Title not available (Why is that?)
- Compressed sensing
- On the Decomposition of Graphs
- Title not available (Why is that?)
- Streaming and communication complexity of clique approximation
- Graph Sparsification in the Semi-streaming Model
- Approximate counting of cycles in streams
- Computing and Combinatorics
- A second look at counting triangles in graph streams
- Title not available (Why is that?)
- Title not available (Why is that?)
- Trading off space for passes in graph streaming problems
- Title not available (Why is that?)
- Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24--28, 2015. Proceedings. Part II
- Estimating Clustering Indexes in Data Streams
- Streaming Lower Bounds for Approximating MAX-CUT
Cited In (6)
- Matroid-constrained vertex cover
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- Independent sets in vertex-arrival streams
- On NP-hardness of the clique partition -- independence number gap recognition and related problems
- Streaming and communication complexity of clique approximation
- Clique Cover and Graph Separation
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)
