Distributed Testing of Distance-k Colorings

DOI10.1007/978-3-030-54921-3_16OpenAlexW3045651373MaRDI QIDQ5100965

Alexandre Nolin, Pierre Fraigniaud, Magnús M. Halldórsson

Publication date: 1 September 2022

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-54921-3_16

zbMATH Keywords

graph coloringdistributed decisiondistributed property testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Related Items (1)

Distributed Symmetry Breaking on Power Graphs via Sparsification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shrinking maxima, decreasing costs: new online packing and covering problems
• An information statistics approach to data stream and communication complexity
• Distributed discovery of large near-cliques
• On the distributional complexity of disjointness
• The local detection paradigm and its applications to self-stabilization
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Distributed testing of excluded subgraphs
• Randomized proof-labeling schemes
• Randomized distributed decision
• Proof labeling schemes
• Optimal distributed all pairs shortest paths and applications
• Beyond set disjointness
• On the power of the congested clique model
• The Complexity of Data Aggregation in Directed Networks
• Online Set Packing
• The Probabilistic Communication Complexity of Set Intersection
• Distributed Verification and Hardness of Distributed Approximation
• A Brief Introduction to Property Testing
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• The Power of Distributed Verifiers in Interactive Proofs
• Interactive Distributed Proofs
• Towards a complexity theory for local distributed computing
• Distance-2 Coloring in the CONGEST Model
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Fast distributed algorithms for testing graph properties

This page was built for publication: Distributed Testing of Distance-k Colorings