Publications - Parallel Incremental Algorithms
You can also find my publication list on Google Scholar and DBLP.
[Back to full publication list]
- 2025:[12] 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), 2025incremental construction for parallel contraction hierarchiesPaper ArXiV Code Slides - 2024:[11] Parallel and (Nearly) Work-Efficient Dynamic Programming
Xiangyun Ding, Yan Gu, and Yihan Sun🏆 Outstanding Paper Award (Best paper finalist)!ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024Software:Parallel Work-Efficient Dynamic Programming [Github]parallelize iterative DP algorithmsPaper ArXiV Code Slides - [10]
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), 2024Parallel CELFPaper ArXiV Code Poster - 2023:[9] Efficient Parallel Output-Sensitive Edit Distance
Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu, and Yihan Sun🏆 Best Paper Award!European Symposium on Algorithms (ESA), 2023DOI:10.4230/LIPIcs.ESA.2023.40Software:Parallel Output-Sensitive Edit Distance [Github]
Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024parallelizing iterative DP algorithmsPaper ArXiV Code Slides - [8]
Parallel Longest Increasing Subsequence and van Emde Boas Trees
Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023DOI:10.1145/3558481.3591069Software:Parallel Longest Increasing Subsequence [Github]Parallelizing sequential algorithms for LISPaper ArXiV Code Slides - 2022:[7] Parallel Cover Trees and Applications
Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022DOI:10.1145/3490148.3538581parallelizing cover tree constructionPaper Slides - [6]
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]Parallelizing sequential algorithms for LIS, activity selection, Huffman tree, MIS, and Dijkstra's algorithm.Paper ArXiV Slides - 2020:[5] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun🏆 Best Paper Candidate!ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020DOI:10.1145/3350755.3400227iterative list ranking algorithmPaper Video Slides - [4]
Randomized Incremental Convex Hull is Highly Parallel
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020DOI:10.1145/3350755.3400255Parallel incremental algorithm for convex hullPaper Video Slides - [3]
Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Journal of the ACM (JACM), 2020DOI:10.1145/3402819Parallel incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE listPaper - 2018:[2] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018DOI:10.1145/3210377.3210380Parallel randomized incremental algorithm on Delaunay triangulationPaper ArXiV - 2016:[1] 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 randomized incremental algorithms for sorting, Delaunay triangulation, closest pair, smallest enclosing disk, SCC, LE listPaper ArXiV