Compact distributed certification of planar graphs
From MaRDI portal
Publication:2037111
DOI10.1007/s00453-021-00823-wOpenAlexW3157038403MaRDI QIDQ2037111
Laurent Feuilloley, Ioan Todinca, Pedro Montealegre, Eric Rémila, Ivan Rapaport, Pierre Fraigniaud
Publication date: 30 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2005.05863
Related Items
Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ Lower bound for constant-size local certification ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed minimum dominating set approximations in restricted families of graphs
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- A new distributed depth-first-search algorithm
- A characterization of planar graphs by Trémaux orders
- The local detection paradigm and its applications to self-stabilization
- Randomized proof-labeling schemes
- Redundancy in distributed proofs
- On distributed Merlin-Arthur decision protocols
- Proof labeling schemes
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Distributed Approximation Algorithms for Planar Graphs
- Fast Distributed Approximations in Planar Graphs
- Efficient Planarity Testing
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- An Upper Bound on Zarankiewicz' Problem
- Distributed Verification and Hardness of Distributed Approximation
- Distributed Dominating Set Approximations beyond Planar Graphs
- The Power of Distributed Verifiers in Interactive Proofs
- Interactive Distributed Proofs
- Distributed Algorithms for Planar Networks I
- Towards a complexity theory for local distributed computing
- Fast approximation algorithms for the diameter and radius of sparse graphs
- What cannot be computed locally!
- Compact Distributed Certification of Planar Graphs
This page was built for publication: Compact distributed certification of planar graphs
