Dynamic constant time parallel graph algorithms with sub-linear work

Jonas Schmidt, Thomas Schwentick

The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and $O(n^{1/2+\epsilon })$ work on the CRCW PRAM model. Th…