A meta-theorem for distributed certification

DOI10.1007/s00453-023-01185-1OpenAlexW4387933027MaRDI QIDQ6182681

Pedro Montealegre, Pierre Fraigniaud, Ivan Rapaport, Ioan Todinca

Publication date: 25 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01185-1

zbMATH Keywords

fault-tolerancedistributed decisionlocally checkable proofproof-labeling scheme

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Graph minors. III. Planar tree-width
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A partial k-arboretum of graphs with bounded treewidth
• The local detection paradigm and its applications to self-stabilization
• What can be verified locally?
• Randomized proof-labeling schemes
• A hierarchy of local decision
• Proof labeling schemes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Deciding First-Order Properties of Nowhere Dense Graphs
• Twin-width I: Tractable FO Model Checking
• The Power of Distributed Verifiers in Interactive Proofs
• Interactive Distributed Proofs
• Towards a complexity theory for local distributed computing
• Approximate proof-labeling schemes

This page was built for publication: A meta-theorem for distributed certification