Wasp: Efficient Asynchronous Single-Source Shortest Path on Multicore Systems via Work Stealing
The Single-Source Shortest Path (SSSP) problem is a fundamental graph problem with an extensive set of real-world applications. State-of-the-art parallel algorithms for SSSP, such as the Δ -stepping algorithm, create parallelism through priority coarsening. Priority coarsening results in redundant computations that diminish the benefits of parallelization and limit parallel scalability.
Authors
- Philippas Tsigas (ORCID: https://orcid.org/0000-0001-9635-9154)
- Son T. (ORCID: https://orcid.org/0000-0003-4599-1525)
- Marco D’Antonio (ORCID: https://orcid.org/0009-0002-7399-7705)
- Hans Vandierendonck (ORCID: https://orcid.org/0000-0001-5868-9259)
Institutions
- Queen's University Belfast (GB)
- Chalmers University of Technology (SE)
Publication Details
- Published
- 2025-11-12
- DOI
- https://doi.org/10.1145/3712285.3759872
- Citations
- 2
- Primary Topic
- Graph Theory and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 2.55