Fast distributed algorithms for testing graph properties

DOI10.1007/978-3-662-53426-7_4zbMath1393.68181arXiv1602.03718OpenAlexW2253610808MaRDI QIDQ5915702

Gregory Schwartzman, Eldar Fischer, Keren Censor-Hillel, Yadu Vasudev

Publication date: 16 August 2018

Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.03718

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (15)

On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Distributed Testing of Distance-k Colorings ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Time-optimal construction of overlay networks ⋮ Unnamed Item ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ On mobile agent verifiable problems ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed discovery of large near-cliques
• The strong perfect graph theorem
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Self-testing/correcting with applications to numerical problems
• Non-local probes do not help with many graph problems
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• A sublinear bipartiteness tester for bounded degree graphs
• Algebraic methods in the congested clique
• Distributed coloring algorithms for triangle-free graphs
• Proof labeling schemes
• Large cuts with local algorithms on triangle-free graphs
• Testing k-colorability
• Randomized Proof-Labeling Schemes
• The communication complexity of distributed task allocation
• Optimal distributed all pairs shortest paths and applications
• On the power of the congested clique model
• Distributedly Testing Cycle-Freeness
• Property testing and its connection to learning and approximation
• Graph Theory and Probability
• Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Testing Triangle-Freeness in General Graphs
• Three theorems regarding testing graph properties
• Distributed Computing: A Locality-Sensitive Approach
• Testing the diameter of graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Tight Bounds for Testing Bipartiteness in General Graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Distributed Verification and Hardness of Distributed Approximation
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Efficient distributed source detection with limited bandwidth
• lgorithmic and Analysis Techniques in Property Testing
• Many Random Walks Are Faster Than One
• Distributed MST and Routing in Almost Mixing Time
• Triangle Finding and Listing in CONGEST Networks
• Distributed Random Walks
• Probability and Computing
• Property testing in bounded degree graphs

This page was built for publication: Fast distributed algorithms for testing graph properties