32 citations · 76 across the 27 of their papers we have counts for
3 papers · 1 filter
Decreasing verification radius in local certification
Laurent Feuilloley, Jan Janoušek, Jan Matyáš Křišťan +1
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verific…
Global certification via perfect hashing
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide i…
Local certification of forbidden subgraphs
Nicolas Bousquet, Linda Cook, Laurent Feuilloley +2
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph de…