Local Certification of Graph Decompositions and Applications to Minor-Free Classes

DOI10.4230/LIPICS.OPODIS.2021.22MaRDI QIDQ6128586zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Laurent Feuilloley, Théo Pierron

Publication date 15 April 2024

Full work available at URL https://hal.science/hal-03610456

zbMATH Keywords

graph decompositionslocal certificationlocally checkable proofsminor-free graphsproof-labeling schemes

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited in

(7)

• The hardness of local certification of finite-state dynamics
• Distributed model checking on graphs of bounded treedepth
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Brief announcement: Distributed model checking on graphs of bounded treedepth
• A subquadratic certification scheme for P₅-free graphs
• Local certification of geometric graph classes
• Distributed complexity of P_k-freeness: decision and certification

This page was built for publication: Local Certification of Graph Decompositions and Applications to Minor-Free Classes

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