Distributed discovery of large near-cliques

DOI10.1007/S00446-011-0132-XMaRDI QIDQ661050zbMATH OpenOpenAlexFDO

Authors Zvika Brakerski, Boaz Patt-Shamir

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

cliquesdense graph detectionprobability of failureprobability of successsubgraph discoveringsynchronous network algorithm

Mathematics Subject Classification ID

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

Recommendations

• Distributed Discovery of Large Near-Cliques
• Distributed algorithms for maximum cliques
• On Distributed Listing of Cliques
• Distributed detection of cliques in dynamic networks
• Finding cliques using few probes
• scientific article; zbMATH DE number 2086259
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Approximation algorithms for maximization problems arising in graph partitioning
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of network synchronization
• Distributed Computing: A Locality-Sensitive Approach
• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• scientific article; zbMATH DE number 5764799 (Why is no real title available?)
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing versus estimation of graph properties
• The dense \(k\)-subgraph problem
• Three theorems regarding testing graph properties
• Tolerant property testing and distance approximation

Cited in

(13)

• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Detecting cliques in CONGEST networks
• Property testing of planarity in the \textsf{CONGEST} model
• A note on improved results for one round distributed clique listing
• Lower bounds for subgraph detection in the CONGEST model
• Distributed Discovery of Large Near-Cliques
• A two-sided error distributed property tester for conductance
• Detecting cliques in CONGEST networks
• Distributed detection of cliques in dynamic networks
• Distributed Testing of Distance-k Colorings
• Deterministic near-optimal distributed listing of cliques
• Stochastic distance in property testing
• Distributed subgraph finding: progress and challenges (invited talk)

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

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