Twenty-Two New Approximate Proof Labeling Schemes (Full Version)

Yuval Emek, Yuval Gil

Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a \emph{proof labeling scheme (PLS)} is a system dedicated to verifying that a given configuration graph satis…