2026-07-23T06:19:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18614 2024-03-06T11:02:16Z ddc:004 open_access

Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work Schmidt, Jonas Schwentick, Thomas Dynamic parallel algorithms Undirected connectivity Bipartiteness The paper proposes dynamic parallel algorithms for connectivity and bipartiteness of undirected graphs that require constant time and 𝒪(n^{1/2+ε}) work on the CRCW PRAM model. The work of these algorithms almost matches the work of the 𝒪(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonas Schmidt and Thomas Schwentick 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.80 urn:nbn:de:0030-drops-186140 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.80 eng https://creativecommons.org/licenses/by/4.0/legalcode