Reductions in local certification

DOI10.1007/978-3-032-11835-6_14MaRDI QIDQ7294430zbMATH OpenFDO

Authors L. Esperet, Sébastien Zeitoun

Publication date 10 July 2026

Full work available at URL https://doi.org/10.1007/978-3-032-11835-6_14

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A meta-theorem for distributed certification
• Compact distributed certification of planar graphs
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Introduction to local certification
• Local certification of geometric graph classes
• Local certification of graphs on surfaces
• Local certification of graphs with bounded genus
• Locally checkable proofs in distributed computing
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Some simplified NP-complete graph problems
• The power of distributed verifiers in interactive proofs
• What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs

This page was built for publication: Reductions in local certification

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