Fast distributed algorithms for testing graph properties
From MaRDI portal
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
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
