Publications - Graph Algorithms
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2025:[21] 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:Orionet: Parallel Single and Batch PPSP [Github]parallel point-to-point shortest paths and batch queries using bidirectional search, A*, and batched bidirectional searchesPaper ArXiV Code - [20]
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:AM-tree: Anti-Monoply tree for incremental MST and temporal connectivity [Github]incremental minimum spanning trees with efficient (O(log n)) update and queries; new solutions for temporal graph processing using incremental MST for various graph problems, such as connectivity, k-connectivity, bipartiteness, etc.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 Finalist!International Conference on Supercomputing (ICS), 2025DOI:10.1145/3721145.3725744Software:SPoCH: Scalable Parallelization of Contraction Hierarchies [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025parallel contraction hierarchiesPaper ArXiV Code Slides - [18]
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: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), 2025parallel k-corePaper ArXiV Code Slides - [17]
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:CBFS: Cluster Breadth-First Search [Github]efficient implementation for parallel cluster BFSPaper ArXiV Code Slides - 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), 2024DOI:10.1145/3626183.3660258Software:PASGAL: Parallel And Scalable Graph Algorithm Library [Github]graph algorithms for strongly connected components (SCC), biconnected components (BCC), single-source shortest paths (SSSP), breadth first search (BFS)Paper ArXiV Code Slides Poster - [15]
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:ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search [Github]graph-based ANNSPaper ArXiV Code - [14]
Fast and Space-Efficient Parallel Algorithms for Influence Maximization
Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
Proceedings of the VLDB Endowment (VLDB), 2024DOI:10.14778/3632093.3632104Software:PaC-IM: Parallel and Compressed Influence Maximization [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024influence maximizationPaper ArXiV Code Poster - 2023:[13] 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: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), 2023High-performance implementation of parallel SCCPaper ArXiV Code Slides Poster - [12]
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: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), 2023Work-, span- and space-efficient algorithm and implementation of parallel biconnected componentsPaper ArXiV Code Poster - 2022:[11] 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:Parallel Dynamic Programming (DP) and greedy algorithms [Github]Implementation of delta-stepping, maximal independent set, graph coloring.Paper ArXiV Slides - [10]
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:CPAM: Compressed Parallel Augmented Maps [Github]Applying PaC-trees for graph streamingPaper ArXiV Code Slides - [9]
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:PBBS: The Problem-Based Benchmark Suite [Github]BFS (breadth-first-search), MIS (maximal independent set), MM (maximal matching), spanning tree, minimum spanning treePaper Code - 2021:[8] 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:Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL [Github]Parallel SSSPPaper Video ArXiV Code Slides - 2020:[7] Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Journal of the ACM (JACM), 2020DOI:10.1145/3402819Parallel SCC, LE listPaper - 2017:[6] Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu, and Yihan Sun
International Colloquium on Automata, Languages, and Programming (ICALP), 2017DOI:10.4230/LIPIcs.ICALP.2017.26approximate SSSP, distance oraclePaper ArXiV - 2016:[5] 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), 2016DOI:10.1145/2935764.2935765Parallel SSSPPaper - [4]
Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016DOI:10.1145/2935764.2935766Parallel SCC, LE listPaper ArXiV - 2015:[3] Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
Yihan Sun, Joseph Crawford, Jie Tang, and Tijana Milenkovic
Workshop on Algorithms in Bioinformatics (WABI), 2015DOI:10.1007/978-3-662-48221-6_2Graph alignment algorithm for PPI network aligningPaper ArXiV - 2014:[2] Fair Evaluation of Global Network Aligners
Joseph Crawford, Yihan Sun, and Tijana Milenkovic
Algorithms for Molecular Biology (AMB), 2014DOI:10.1145/2755573.2755597Comparing graph alignment algorithms for PPI network aligningPaper ArXiV - 2013:[1] Influence Maximization in Dynamic Social Networks
Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang, and Xiaoming Sun
IEEE International Conference on Data Mining (ICDM), 2013DOI:10.1109/ICDM.2013.145Influence maximization on social networksPaper ArXiV Slides