Compact distributed certification of planar graphs

DOI10.1007/S00453-021-00823-WMaRDI QIDQ2037111zbMATH OpenOpenAlexFDO

Authors Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Eric Rémila, Ioan Todinca

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

distributed algorithmsplanaritylabeling schemesnetwork algorithmsgraph property certification

Mathematics Subject Classification ID

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

Recommendations

• Proof labeling schemes
• Introduction to local certification
• Randomized proof-labeling schemes
• Proof labeling schemes
• Randomized proof-labeling schemes

Cites work

• scientific article; zbMATH DE number 6820307 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A characterization of planar graphs by Trémaux orders
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A new distributed depth-first-search algorithm
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• An Upper Bound on Zarankiewicz' Problem
• Compact Distributed Certification of Planar Graphs
• Distributed Approximation Algorithms for Planar Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed algorithms for planar networks. I: Planar embedding
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed minimum dominating set approximations in restricted families of graphs
• Distributed verification and hardness of distributed approximation
• Efficient Planarity Testing
• Fast Distributed Approximations in Planar Graphs
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Interactive distributed proofs
• Local verification of global proofs
• Locally checkable proofs in distributed computing
• Near-optimal distributed DFS in planar graphs
• On distributed Merlin-Arthur decision protocols
• Proof labeling schemes
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Survey of distributed decision
• The local detection paradigm and its applications to self-stabilization
• The power of distributed verifiers in interactive proofs
• Towards a complexity theory for local distributed computing
• Trade-offs in distributed interactive proofs
• What can be verified locally?
• What cannot be computed locally!

Cited in

(15)

• Introduction to local certification
• Local certification of graphs with bounded genus
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• A hierarchy of local decision
• Brief announcement: Distributed model checking on graphs of bounded treedepth
• Locally verifiable distributed SNARGs
• Local certification of geometric graph classes
• The power of distributed verifiers in interactive proofs
• Redundancy in distributed proofs
• A subquadratic certification scheme for P₅-free graphs
• Distributed model checking on graphs of bounded treedepth
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Compact distributed certification of geometric graph classes

This page was built for publication: Compact distributed certification of planar graphs

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