Compact distributed certification of planar graphs

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

zbMATH Keywords

planaritydistributed algorithmsnetwork algorithmslabeling schemesgraph property certification

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

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