Introduction to local certification
From MaRDI portal
Publication:5024672
DOI10.46298/dmtcs.6280zbMath1481.05148arXiv1910.12747OpenAlexW2981544750MaRDI QIDQ5024672
Publication date: 27 January 2022
Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.12747
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14)
Related Items
Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ Labeling schemes for deterministic radio multi-broadcast ⋮ Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width ⋮ Lower bound for constant-size local certification
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast and compact self-stabilizing verification, computation, and fault detection of an MST
- Tree exploration with advice
- Parallel \((\Delta +1)\)-coloring of constant-degree graphs
- The local detection paradigm and its applications to self-stabilization
- Node labels in local decision
- What can be verified locally?
- Space-time tradeoffs for distributed verification
- Memory requirements for silent stabilization
- Distributed verification of minimum spanning trees
- Randomized proof-labeling schemes
- Compact distributed certification of planar graphs
- A hierarchy of local decision
- Randomized distributed decision
- Proof labeling schemes
- Distributed computing with advice: information sensitivity of graph coloring
- Distributedly Testing Cycle-Freeness
- Deterministic coin tossing with applications to optimal parallel list ranking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- Communication Complexity
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Proof-Labeling Schemes: Broadcast, Unicast and in Between
- The Power of Distributed Verifiers in Interactive Proofs
- What can be decided locally without identifiers?
- Proof labeling schemes
- Oracle size
- Interactive Distributed Proofs
- Computational Complexity
- Towards a complexity theory for local distributed computing
- On the Impact of Identifiers on Local Decision
- Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
- Compact Distributed Certification of Planar Graphs
- Approximate proof-labeling schemes
- Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
This page was built for publication: Introduction to local certification
