Distributed discovery of large near-cliques

DOI10.1007/s00446-011-0132-xzbMath1231.68066OpenAlexW2025809519MaRDI QIDQ661050

Boaz Patt-Shamir, Zvika Brakerski

Publication date: 6 February 2012

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-011-0132-x

zbMATH Keywords

cliquesprobability of failureprobability of successdense graph detectionsubgraph discoveringsynchronous network algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (9)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Distributed Testing of Distance-k Colorings ⋮ Unnamed Item ⋮ Detecting cliques in CONGEST networks ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Tolerant property testing and distance approximation
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Property testing and its connection to learning and approximation
• Testing versus estimation of graph properties
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Complexity of network synchronization
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Three theorems regarding testing graph properties
• Distributed Computing: A Locality-Sensitive Approach
• Robust Characterizations of Polynomials with Applications to Program Testing
• The dense \(k\)-subgraph problem

This page was built for publication: Distributed discovery of large near-cliques