Three notes on distributed property testing

DOI10.4230/LIPICS.DISC.2017.15zbMATH Open1515.68365MaRDI QIDQ6487486FDOQ6487486

Authors: Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, Ioan Todinca 

Publication date: 3 February 2023

Recommendations

• Distributed testing of excluded subgraphs
• Fast distributed algorithms for testing graph properties
• Fast distributed algorithms for testing graph properties
• Property testing of planarity in the \textsf{CONGEST} model
• Property testing of planarity in the \textsf{CONGEST} model

zbMATH Keywords

distributed algorithmsproperty testingCONGEST modelproperty correcting

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Cited In (15)

• Deciding and verifying network properties locally with few output bits
• On the power of threshold-based algorithms for detecting cycles in the CONGEST model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Title not available (Why is that?)
• Property testing of planarity in the \textsf{CONGEST} model
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Detecting cliques in CONGEST networks
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Lower Bounds for Subgraph Detection in the CONGEST Model
• Deterministic near-optimal distributed listing of cliques
• Title not available (Why is that?)
• Distribution-Free Property-Testing
• Title not available (Why is that?)
• On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model

This page was built for publication: Three notes on distributed property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487486)