
arXiv: 2307.10107
The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and $O(n^{1/2+ε})$ work on the 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, we show 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.
FOS: Computer and information sciences, Bipartiteness, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Dynamic parallel algorithms, Undirected connectivity, 004, ddc: ddc:004
FOS: Computer and information sciences, Bipartiteness, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Dynamic parallel algorithms, Undirected connectivity, 004, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
