Distributedly testing cycle-freeness

DOI10.1007/978-3-319-12340-0_2MaRDI QIDQ2945176zbMATH OpenOpenAlexFDO

Authors Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, Fabien Mathieu

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-12340-0_2

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Three notes on distributed property testing
• Distributed testing of excluded subgraphs
• Property testing of planarity in the \textsf{CONGEST} model

Cited in

(12)

• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Deciding and verifying network properties locally with few output bits
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• A hierarchy of local decision
• Proof-labeling schemes: broadcast, unicast and in between
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
• Distributed Cycle Detection and Removal
• Introduction to local certification
• Redundancy in distributed proofs
• The impact of locality in the broadcast congested clique model
• Approximate proof-labeling schemes

This page was built for publication: Distributedly testing cycle-freeness

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