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

DOI10.1007/s00453-017-0277-5zbMath1391.68048OpenAlexW2577465605MaRDI QIDQ1709587

Tejasvam Singh, Zaoxing Liu, N. V. Vinodchandran, Vladimir Braverman, 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

cliquecommunication complexitygraph decompositiontriangle countingstreaming algorithm

Mathematics Subject Classification ID

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

Related Items (2)

Matroid-constrained vertex cover ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A second look at counting triangles in graph streams
• Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24--28, 2015. Proceedings. Part II
• Streaming and Communication Complexity of Clique Approximation
• Approximate Counting of Cycles in Streams
• Estimating Clustering Indexes in Data Streams
• Graph Sparsification in the Semi-streaming Model
• On the Decomposition of Graphs
• Streaming Lower Bounds for Approximating MAX-CUT
• Computing and Combinatorics
• Compressed sensing
• Trading off space for passes in graph streaming problems

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