Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

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

Even, G., Levi, R., & Medina, M. (2017). Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model. Retrieved from http://arxiv.org/abs/1705.04898.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier
Latex : {Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model}

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1705.04898.pdf (Preprint), 210KB
Name:
arXiv:1705.04898.pdf
Beschreibung:
File downloaded from arXiv at 2019-02-04 08:47
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Even, Guy1, Autor           
Levi, Reut2, Autor           
Medina, Moti2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC,Computer Science, Data Structures and Algorithms, cs.DS
 Zusammenfassung: 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. We then apply this procedure to obtain an optimal
tester, in terms of $n$, for testing bipartiteness, whose round complexity is
$O(\epsilon^{-1}\log n)$, which improves over the $poly(\epsilon^{-1} \log
n)$-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, for
cycle-freeness, we obtain a \emph{corrector} of the graph that locally corrects
the graph so that the corrected graph is acyclic. Note that, unlike a tester, a
corrector needs to mend the graph in many places in the case that the graph is
far from having the property.
In the second part of the paper we design algorithms for testing whether the
network is $H$-free for any connected $H$ of size up to four with round
complexity of $O(\epsilon^{-1})$. This improves over the
$O(\epsilon^{-2})$-round algorithms for testing triangle freeness by
Censor-Hillel et al. (DISC 2016) and for testing excluded graphs of size $4$ by
Fraigniaud et al. (DISC 2016).
In the last part we generalize the global tester by Iwama and Yoshida (ITCS
2014) of testing $k$-path freeness to testing the exclusion of any tree of
order $k$. We then show how to simulate this algorithm in the CONGEST-model in
$O(k^{k^2+1}\cdot\epsilon^{-k})$ rounds.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2017-05-132017
 Publikationsstatus: Online veröffentlicht
 Seiten: 14 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1705.04898
URI: http://arxiv.org/abs/1705.04898
BibTex Citekey: DBLP:journals/corr/EvenLM17
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: