Local certification of graphs with bounded genus

DOI10.1016/j.dam.2022.10.004OpenAlexW3043691737MaRDI QIDQ2104916

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

Publication date: 8 December 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.08084

zbMATH Keywords

distributed graph algorithmslocal certificationproof-labeling schemelocally checkable proofs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• Sparsity. Graphs, structures, and algorithms
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• The local detection paradigm and its applications to self-stabilization
• What can be verified locally?
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Compact distributed certification of planar graphs
• Local certification of graphs on surfaces
• A meta-theorem for distributed certification
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• A hierarchy of local decision
• 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
• Embeddability of arrangements of pseudocircles into the sphere
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Fast Distributed Approximations in Planar Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
• What Can be Computed Locally?
• Distributed Verification and Hardness of Distributed Approximation
• Distributed Dominating Set Approximations beyond Planar Graphs
• Adjacency Labelling for Planar Graphs (and Beyond)
• Shorter Labeling Schemes for Planar Graphs
• The Power of Distributed Verifiers in Interactive Proofs
• Interactive Distributed Proofs
• Distributed Algorithms for Planar Networks I
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs
• Distributed Computing
• Towards a complexity theory for local distributed computing
• Distributed Almost Exact Approximations for Minor-Closed Families
• What cannot be computed locally!
• Approximate proof-labeling schemes

This page was built for publication: Local certification of graphs with bounded genus