Dynamic constant-time parallel graph algorithms with sub-linear work

The talk proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant-time and n^{1/2} times polylog(n) work on the (arbitrary) CRCW PRAM model. The work of these algorithms almost matches the work of the O(log n) time algorithm for Connectivity by Kopelowitz et al. (2018) on the EREW PRAM model and the time of the sequential algorithm for bipartiteness by Eppstein et al. (1997). In particular, it is shown that the sparsification technique, which has been used in both mentioned papers, can in principle also be used for constant time algorithms in the CRCW PRAM model, despite the logarithmic depth of sparsification trees. This talk presents yet unpublished joined work with Thomas Schwentick. Contributed talk given by Jonas Schmidt

Authors

• Jonas Schmidt

Keywords

No keywords are indexed for this paper.