Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • 3. UTUCris-artikkelit
  • Rinnakkaistallenteet
  • Näytä aineisto
  •   Etusivu
  • 3. UTUCris-artikkelit
  • Rinnakkaistallenteet
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

Distributed Testing of Excluded Subgraphs

Ville Salo; Ivan Rapaport; Pierre Fraigniaud; Ioan Todinca

Distributed Testing of Excluded Subgraphs

Ville Salo
Ivan Rapaport
Pierre Fraigniaud
Ioan Todinca
Katso/Avaa
1605.03719v1.pdf (220.2Kb)
Lataukset: 

doi:10.1007/978-3-662-53426-7_25
URI
http://link.springer.com/chapter/10.1007/978-3-662-53426-7_25
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042716180
Tiivistelmä

We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangle-freeness. Hence, in particular, testing whether a graph is K4-free, and testing whether a graph is C4-free can be done in a constant number of rounds (where Kk denotes the k-node clique, and Ck denotes the k-node cycle). On the other hand, we show that testing Kk-freeness and Ck-freeness for k≥5 appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test Kk-freeness and Ck-freeness in a constant number of rounds for k≥5.

Kokoelmat
  • Rinnakkaistallenteet [19207]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste