English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we present distributed testing algorithms of graph propertiesin the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided errortesting algorithms in the general graph model.  We first describe a general procedure for converting $\epsilon$-testers witha 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 ofprocessors of the network. We then apply this procedure to obtain an optimaltester, in terms of $n$, for testing bipartiteness, whose round complexity is$O(\epsilon^{-1}\log n)$, which improves over the $poly(\epsilon^{-1} \logn)$-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, forcycle-freeness, we obtain a \emph{corrector} of the graph that locally correctsthe graph so that the corrected graph is acyclic. Note that, unlike a tester, acorrector needs to mend the graph in many places in the case that the graph isfar from having the property.  In the second part of the paper we design algorithms for testing whether thenetwork is $H$-free for any connected $H$ of size up to four with roundcomplexity of $O(\epsilon^{-1})$. This improves over the$O(\epsilon^{-2})$-round algorithms for testing triangle freeness byCensor-Hillel et al. (DISC 2016) and for testing excluded graphs of size $4$ byFraigniaud et al. (DISC 2016).  In the last part we generalize the global tester by Iwama and Yoshida (ITCS2014) of testing $k$-path freeness to testing the exclusion of any tree oforder $k$. We then show how to simulate this algorithm in the CONGEST-model in$O(k^{k^2+1}\cdot\epsilon^{-k})$ rounds.

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