3 papers
cs.DC2026
A Note on Diameter Certification in Trees
Josef Erik Sedláček
In the local certification model, certifying the diameter of general graphs requires large certificates, but trees admit more efficient solutions. In this note, we provide a -lo…
cs.DC2025
Proving there is a leader without naming it
Laurent Feuilloley, Josef Erik Sedláček, Martin Slávik
Local certification is a mechanism for certifying to the nodes of a network that a certain property holds. In this framework, nodes are assigned labels, called certificates, which…
cs.DC2024
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…