Local certification of graphs with bounded genus

DOI10.1016/J.DAM.2022.10.004MaRDI QIDQ2104916zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Compact distributed certification of planar graphs
• Local certification of graphs on surfaces
• The power of distributed verifiers in interactive proofs
• Interactive distributed proofs
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs

Cites work

• scientific article; zbMATH DE number 4047749 (Why is no real title available?)
• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• scientific article; zbMATH DE number 49719 (Why is no real title available?)
• A hierarchy of local decision
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• A local constant factor MDS approximation for bounded genus graphs
• A meta-theorem for distributed certification
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Adjacency Labelling for Planar Graphs (and Beyond)
• Approximate proof-labeling schemes
• Compact distributed certification of planar graphs
• Distributed Almost Exact Approximations for Minor-Closed Families
• Distributed Computing
• 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
• Embeddability of arrangements of pseudocircles into the sphere
• Fast Distributed Approximations in Planar Graphs
• Graphs on surfaces
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Interactive distributed proofs
• Local certification of graphs on surfaces
• Locally checkable proofs in distributed computing
• Near-optimal distributed DFS in planar graphs
• On distributed Merlin-Arthur decision protocols
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• Probabilistic embeddings of bounded genus graphs into planar graphs
• Proof labeling schemes
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Shorter Labeling Schemes for Planar Graphs
• Sparsity. Graphs, structures, and algorithms
• 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 Computed Locally?
• What can be verified locally?
• What cannot be computed locally!

Cited in

(1)

• Planarity can be verified by an approximate proof labeling scheme in constant-time

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

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