Semi-Streaming Algorithms for Graph Property Certification

Avinandan Das, Pierre Fraigniaud, Ami Paz +1

We introduce the {\em certification} of solutions to graph problems when access to the input is restricted. This topic has received a lot of attention in the distributed computing…