Publications - Graph Algorithms
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2027:[23]Toggle Tree: A New Data Structure for Efficient Parallel Graph Processing
Xinjian Jiang, Youzhe Liu, Yan Gu, and Yihan Sun
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2027 - [22]Use Your Time(stamp) Wisely: The GraphTide Real-World Dynamic Graph Datasets
Brian Wheatman, Quinten De Man, Xiangyun Ding, Zhongqi Wang, Randal Burns, Laxman Dhulipala, Xiaojun Dong, Yan Gu, Yihan Sun, and Letong Wang
Proceedings of the VLDB Endowment (PVLDB), Vol. 20, 2027 - 2025:[21]Parallel Point-to-Point Shortest Paths and Batch Queries
Xiaojun Dong, Andy Li, Yan Gu, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025
Conference paper Full version (arXiv) Code - [20]New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
Xiangyun Ding, Yan Gu, and Yihan Sun
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025incremental minimum spanning trees, applications on temporal connectivity, k-connectivity, bipartiteness, etc.Conference paper Code - [19]Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, and Yihan Sun🏆 Best Paper FinalistACM International Conference on Supercomputing (ICS), 2025
Conference paper Full version (arXiv) Code - [18]Parallel k-Core Decomposition: Theory and Practice
Youzhe Liu, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2025
Conference paper Full version (arXiv) Code - [17]Parallel Cluster-BFS and Applications to Shortest Paths
Letong Wang, Guy E. Blelloch, Yan Gu, and Yihan Sun
SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), 2025
Conference paper Full version (arXiv) Code - 2024:[16]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), 2024
Conference paper Full version (arXiv) Code - [15]Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
Proceedings of the VLDB Endowment (PVLDB), 17(3), 2024
Conference paper Full version (arXiv) Code - [14]ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms
Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024
Conference paper Full version (arXiv) Code - 2023:[13]Parallel Strong Connectivity Based on Faster Reachability
Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
ACM International Conference on Management of Data (SIGMOD), 2023Theoretical and practical parallel SCC algorithmsConference paper Full version (arXiv) Code - [12]Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun🏆 Best Paper AwardACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023Theoretical and practical parallel biconnectivity algorithmsConference paper Full version (arXiv) Code - 2021:[11]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), 2021Theoretical and practical parallel SSSP algorithmsConference paper Full version (arXiv) Video Code - [10]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, Vol. 55 Issue 1, pp. 38-46, 2021Enable parallel graph processing for geometric dataConference paper Code - [9]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), 2021Traingle counting, SCC, FRT trees from graphsConference paper - 2020:[8]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🏆 Memorable Paper Award Finalist at the Non-Volatile Memories Workshop (NVMW'20)Proceedings of the VLDB Endowment (PVLDB), 13(9), 202019 commonly used graph algorithmsConference paper Full version (arXiv) Code - [7]Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Journal of the ACM (JACM), 67(5), 2020Parallel SCC, LE-listsConference paper Journal paper - 2018:[6]Implicit Decomposition for Write-Efficient Connectivity Algorithms
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018Graph connectivity and biconnectivityConference paper Full version (arXiv) - 2017:[5]Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu, and Yihan Sun
International Colloquium on Automata, Languages, and Programming (ICALP), 2017approximate SSSP, distance oracleConference paper Full version (arXiv) - 2016:[4]Parallel Shortest-paths Using Radius Stepping
Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016Parallel SSSPConference paper - [3]Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016Parallel SCC, LE-listsConference paper Full version (arXiv) - [2]Parallel Algorithms with Asymmetric Read and Write Costs
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016BFSConference paper - [1]Efficient Algorithms with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun
European Symposium on Algorithms (ESA), 2016SSSP, MSTConference paper Full version (arXiv)