Local certification of graphs with bounded genus

DOI10.1016/J.DAM.2022.10.004OpenAlexW3043691737MaRDI QIDQ2104916FDOQ2104916

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

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

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)

Cites Work

• Proof labeling schemes
• Graphs on surfaces
• Title not available (Why is that?)
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Sparsity. Graphs, structures, and algorithms
• What cannot be computed locally!
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast Distributed Approximations in Planar Graphs
• Distributed minimum dominating set approximations in restricted families of graphs
• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed Almost Exact Approximations for Minor-Closed Families
• The local detection paradigm and its applications to self-stabilization
• 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
• Distributed Computing
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Probabilistic embeddings of bounded genus graphs into planar graphs
• What Can be Computed Locally?
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• Shorter Labeling Schemes for Planar Graphs
• Towards a complexity theory for local distributed computing
• Embeddability of arrangements of pseudocircles into the sphere
• A hierarchy of local decision
• What can be verified locally?
• A local constant factor MDS approximation for bounded genus graphs
• Locally checkable proofs in distributed computing
• Randomized proof-labeling schemes
• On distributed Merlin-Arthur decision protocols
• Interactive distributed proofs
• Redundancy in distributed proofs
• The power of distributed verifiers in interactive proofs
• Approximate proof-labeling schemes
• Trade-offs in distributed interactive proofs
• Compact distributed certification of planar graphs
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed algorithms for planar networks. I: Planar embedding
• Near-optimal distributed DFS in 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
• Adjacency Labelling for Planar Graphs (and Beyond)

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)