Compact distributed certification of planar graphs
type: Item
instance of: scholarly article
title: Compact distributed certification of planar graphs
author: Laurent Feuilloley
author: Pierre Fraigniaud
author: Pedro Montealegre
author: Ivan Rapaport
author: Eric Rémila
author: Ioan Todinca
published in: Algorithmica
publication date: 2021-06-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/2005.05863
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7365275
zbMATH Keywords: distributed algorithms
zbMATH Keywords: network algorithms
zbMATH Keywords: graph property certification
zbMATH Keywords: labeling schemes
zbMATH Keywords: planarity
MaRDI profile type: Publication
OpenAlex ID: W3157038403
cites work: The local detection paradigm and its applications to self-stabilization
cites work: Distributed Dominating Set Approximations beyond Planar Graphs
cites work: A new distributed depth-first-search algorithm
cites work: Q4636605
cites work: Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
cites work: Distributed Approximation Algorithms for Planar Graphs
cites work: Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
cites work: Fast Distributed Approximations in Planar Graphs
cites work: Q4947393
cites work: Q4967211
cites work: Q4598260
cites work: Redundancy in distributed proofs
cites work: Compact Distributed Certification of Planar Graphs
cites work: Q5090917
cites work: Towards a complexity theory for local distributed computing
cites work: On distributed Merlin-Arthur decision protocols
cites work: Randomized proof-labeling schemes
cites work: A characterization of planar graphs by Trémaux orders
cites work: An Upper Bound on Zarankiewicz' Problem
cites work: Distributed Algorithms for Planar Networks I
cites work: Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
cites work: Q3179347
cites work: Efficient Planarity Testing
cites work: Interactive Distributed Proofs
cites work: Proof labeling schemes
cites work: What cannot be computed locally!
cites work: Distributed minimum dominating set approximations in restricted families of graphs
cites work: The Power of Distributed Verifiers in Interactive Proofs
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
cites work: Fast approximation algorithms for the diameter and radius of sparse graphs
cites work: Distributed Verification and Hardness of Distributed Approximation
cites work: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
cites work: Trade-offs in distributed interactive proofs
cites work: Near-optimal distributed DFS in planar graphs
DOI: 10.1007/S00453-021-00823-W
description: scientific article; zbMATH DE number 7365275