New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory

DOI10.1007/978-3-662-48054-0_13zbMath1466.68055OpenAlexW1588634370MaRDI QIDQ2946384

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

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_13

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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) Communication complexity, information complexity (68Q11)

Cites Work

• A second look at counting triangles in graph streams
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory