Graph Algorithms
[Back to full publication list]
- 2025:[19] Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear)
Xiaojun Dong*, Andy Li*, Yan Gu*, and Yihan Sun*
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025DOI:10.1145/3694906.3743311Software Library:Orionet: Parallel Single and Batch PPSP [Github]
Paper ArXiV Code -
[18]
New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear)
Xiangyun Ding*, Yan Gu*, and Yihan Sun*
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025Software Library:AM-tree: Anti-Monoply tree for incremental MST and temporal connectivity [Github]
Paper Code -
[17]
Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan*, Xiaojun Dong*, Letong Wang*, Enzuo Zhu*, Yan Gu*, and Yihan Sun*🏆 Best Paper Finalist!International Conference on Supercomputing (ICS), 2025DOI:10.1145/3721145.3725744Software Library:SPoCH: Scalable Parallelization of Contraction Hierarchies [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides -
[16]
Parallel k-Core Decomposition: Theory and Practice
Youzhe Liu*, Xiaojun Dong*, Yan Gu*, and Yihan Sun*
ACM Special Interest Group on Management of Data (SIGMOD), 2025DOI:10.1145/3725332Software Library:Parallel k-core implementation, integrated in PASGAL [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
Paper ArXiV Code Slides -
[15]
Parallel Cluster-BFS and Applications to Shortest Paths
Letong Wang*, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
Algorithm Engineering and Experiments (ALENEX), 2025DOI:10.1137/1.9781611978339.4Software Library:CBFS: Cluster Breadth-First Search [Zenodo]
Paper ArXiV Code Slides - 2024:[14] Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
Xiaojun Dong*, Yan Gu*, Yihan Sun*, and Letong Wang*
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024Software Library:PASGAL: Parallel And Scalable Graph Algorithm Library [Github]
Paper ArXiV Code Slides Poster -
[13]
BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers
Brian Wheatman, Xiaojun Dong*, Zheqi Shen*, Laxman Dhulipala, Jakub Łącki, Prashant Pandey, and Helen Xu
International Conference on Very Large Data Bases (VLDB), 2024DOI:10.14778/3665844.3665859Software Library:BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers [Github]
Paper ArXiV Code -
[12]
ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search
Magdalen Dobson Manohar, Zheqi Shen*, , Laxman Dhulipala, Yan Gu*, Harsha Simhadri, and Yihan Sun*
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024DOI:10.1145/3627535.3638475Software Library:ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search [Github]
Paper ArXiV Code -
[11]
Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang*, Xiangyun Ding*, Yan Gu*, and Yihan Sun*
International Conference on Very Large Data Bases (VLDB), 2024DOI:10.14778/3632093.3632104Software Library:PaC-IM: Parallel and Compressed Influence Maximization [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
Paper ArXiV Code Poster - 2023:[10] Parallel Strong Connectivity Based on Faster Reachability
Letong Wang*, Xiaojun Dong*, Yan Gu*, and Yihan Sun*
ACM Special Interest Group on Management of Data (SIGMOD), 2023DOI:10.1145/3589259Software Library:Parallel Strongly Connected Components (SCC), integrated in PASGAL [Github]
Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
Poster presented at the Highlights of Parallel Computing (HOPC@SPAA), 2023
Paper ArXiV Code Slides Poster -
[9]
Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong*, Letong Wang*, Yan Gu*, and Yihan Sun*🏆 Best Paper Award!ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023DOI:10.1145/3572848.3577483Software Library:Parallel Biconnected Components (BCC), integrated in PASGAL [Github]
Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2023
Paper ArXiV Code Poster - 2022:[8] Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
Zheqi Shen*, Zijin Wan*, Yan Gu*, and Yihan Sun*
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022DOI:10.1145/3490148.3538574Software Library:Parallel Dynamic Programming (DP) and greedy algorithms [Github]
Paper ArXiV Slides -
[7]
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
ACM Conference on Programming Language Design and Implementation (PLDI), 2022DOI:10.1145/3519939.3523733Software Library:CPAM: Compressed Parallel Augmented Maps [Github]
Paper ArXiV Code Slides -
[6]
POSTER: The Problem-Based Benchmark Suite (PBBS), V2
Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson Manohar, and Yihan Sun*
ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022DOI:10.1145/3503221.3508422Software Library:PBBS: The Problem-Based Benchmark Suite [Github]
Paper Code - 2021:[5] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong*, Yan Gu*, Yihan Sun*, and Yunming Zhang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021DOI:10.1145/3409964.3461782Software Library:Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL [Github]
Paper Video ArXiV Code Slides -
[4]
GeoGraph: A Framework for Graph Processing on Geometric Data
Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu*, and Julian Shun
ACM SIGOPS Operating Systems Review (SIGOPS-OSR), 2021Software Library:GeoGraph: A Framework for Graph Processing on Geometric Data [Github]
Paper Code -
[3]
The Read-Only Semi-External Model
Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu*, Charles McGuffey, and Julian Shun
ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021
Paper - 2020:[2] Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu*, Julian Shun, and Yihan Sun*
Journal of the ACM (JACM), 2020DOI:10.1145/3402819
Paper -
[1]
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu*, Guy E. Blelloch, Phillip B. Gibbons, and Julian Shun
International Conference on Very Large Data Bases (VLDB), 2020Software Library:SAGE: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs [Github]
Paper ArXiV Code