Log Diameter Rounds MST Verification and Sensitivity in MPC

Sam Coy, Artur Czumaj, Gopinath Mishra +1

We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the se…