Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model

Understand

In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al.

• 2016].
• We present one-sided error testing algorithms in the general graph model.
• We first describe a general procedure for converting $\epsilon$-testers with a number of rounds $f(D)$, where $D$ denotes the diameter of the graph, to $O((\log n)/\epsilon)+f((\log n)/\epsilon)$ rounds, where $n$ is the number of processors of the network.