Local certification of graphs with bounded genus
type: Item
instance of: scholarly article
title: Local certification of graphs with bounded genus
author: Laurent Feuilloley
author: Pierre Fraigniaud
author: Pedro Montealegre
author: Ivan Rapaport
author: Eric Rémila
author: Ioan Todinca
published in: Discrete Applied Mathematics
publication date: 2022-12-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/2007.08084
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7628632
zbMATH Keywords: distributed graph algorithms
zbMATH Keywords: local certification
zbMATH Keywords: proof-labeling scheme
zbMATH Keywords: locally checkable proofs
MaRDI profile type: Publication
OpenAlex ID: W3043691737
cites work: Distributed Computing
cites work: The local detection paradigm and its applications to self-stabilization
cites work: A Local Constant Factor MDS Approximation for Bounded Genus Graphs
cites work: Distributed Dominating Set Approximations beyond Planar Graphs
cites work: What can be verified locally?
cites work: Shorter Labeling Schemes for Planar Graphs
cites work: Approximate proof-labeling schemes
cites work: Distributed Almost Exact Approximations for Minor-Closed Families
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: Adjacency Labelling for Planar Graphs (and Beyond)
cites work: Planarity can be verified by an approximate proof labeling scheme in constant-time
cites work: Local certification of graphs on surfaces
cites work: A hierarchy of local decision
cites work: Redundancy in distributed proofs
cites work: Compact distributed certification of planar graphs
cites work: Towards a complexity theory for local distributed computing
cites work: On distributed Merlin-Arthur decision protocols
cites work: A meta-theorem for distributed certification
cites work: Randomized proof-labeling schemes
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: Q3602875
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: Q3999514
cites work: Graphs on surfaces
cites work: The Power of Distributed Verifiers in Interactive Proofs
cites work: What Can be Computed Locally?
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Embeddability of arrangements of pseudocircles into the sphere
cites work: Q3784090
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: 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: A local approximation algorithm for minimum dominating set problem in anonymous planar networks
cites work: Q3847965
cites work: Trade-offs in distributed interactive proofs
cites work: Near-optimal distributed DFS in planar graphs
DOI: 10.1016/J.DAM.2022.10.004
description: scientific article; zbMATH DE number 7628632