A Deterministic Work-Depth Tradeoff for Strongly Connected Components
In this paper, we show the first deterministic parallel algorithm for computing the strongly connected components (SCCs) of a directed graph beyond the full transitive closure computation. For any parameter t ϵ [1, n], the algorithm can identify the SCCs within Õ(nt2 + m) work and Õ(n/t) depth. This matches (up to polylogarithmic factors) the state-of-the-art deterministic tradeoff for st-reachability and solves an open problem of Spencer [J. ACM '97].
Authors
- Adam Karczmarz (ORCID: https://orcid.org/0000-0002-2693-8713)
- B. Lewandowski
Institutions
- Warsaw University of Technology (PL)
- University of Warsaw (PL)
Publication Details
- Published
- 2025-07-16
- DOI
- https://doi.org/10.1145/3694906.3743350
- Primary Topic
- Manufacturing Process and Optimization
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Narodowe Centrum Badań i Rozwoju