Parallelism in Sequential Algorithms

[Back to full publication list]

• 2025:
  [10] Parallel Contraction Hierarchies Can Be Efficient and Scalable
  Zijin Wan*, Xiaojun Dong*, Letong Wang*, Enzuo Zhu*, Yan Gu*, and Yihan Sun*
  
  🏆 Best Paper Finalist!
  ICS
   International Conference on Supercomputing (ICS), 2025    [BibTeX]
  @inproceedings{ Wan2025Parallel,
  title = { Parallel Contraction Hierarchies Can Be Efficient and Scalable },
  author = { Wan, Zijin and  Dong, Xiaojun and  Wang, Letong and  Zhu, Enzuo and  Gu, Yan and  Sun, Yihan},
  booktitle = {International Conference on Supercomputing (ICS)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3721145.3725744    [copy]
  
    Software Library:
  SPoCH: Scalable Parallelization of Contraction Hierarchies  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
  Paper   ArXiV  Code  Slides  
• 2024:
  [9] Parallel and (Nearly) Work-Efficient Dynamic Programming
  Xiangyun Ding*, Yan Gu*, and Yihan Sun*
  
  🏆 Outstanding Paper Award (Best paper finalist)!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Ding2024Parallel,
  title = { Parallel and (Nearly) Work-Efficient Dynamic Programming },
  author = { Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software Library:
  Parallel Work-Efficient Dynamic Programming  [Github]
  Paper   ArXiV  Code  Slides  
• [8] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
  Letong Wang*, Xiangyun Ding*, Yan Gu*, and Yihan Sun*
  
  VLDB
   International Conference on Very Large Data Bases (VLDB), 2024    [BibTeX]
  @inproceedings{ Wang2024Fast,
  title = { Fast and Space-Efficient Parallel Algorithms for Influence Maximization },
  author = { Wang, Letong and  Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.14778/3632093.3632104    [copy]
  
    Software Library:
  PaC-IM: Parallel and Compressed Influence Maximization  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Poster  
• 2023:
  [7] Efficient Parallel Output-Sensitive Edit Distance
  Xiangyun Ding*, Xiaojun Dong*, Yan Gu*, Youzhe Liu*, and Yihan Sun*
  
  🏆 Best Paper Award!
  ESA
   European Symposium on Algorithms (ESA), 2023    [BibTeX]
  @inproceedings{ Ding2023Efficient,
  title = { Efficient Parallel Output-Sensitive Edit Distance },
  author = { Ding, Xiangyun and  Dong, Xiaojun and  Gu, Yan and  Liu, Youzhe and  Sun, Yihan},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.ESA.2023.40    [copy]
  
    Software Library:
  Parallel Output-Sensitive Edit Distance  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  Paper   ArXiV  Code  Slides  
• [6] Parallel Longest Increasing Subsequence and van Emde Boas Trees
  Yan Gu*, Ziyang Men*, Zheqi Shen*, Yihan Sun*, and Zijin Wan*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023    [BibTeX]
  @inproceedings{ Gu2023Parallel,
  title = { Parallel Longest Increasing Subsequence and van Emde Boas Trees },
  author = { Gu, Yan and  Men, Ziyang and  Shen, Zheqi and  Sun, Yihan and  Wan, Zijin},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3558481.3591069    [copy]
  
    Software Library:
  Parallel Longest Increasing Subsequence  [Github]
  Paper   ArXiV  Code  Slides  
• 2022:
  [5] Parallel Cover Trees and Applications
  Yan Gu*, Zachary Napier, Yihan Sun*, and Letong Wang*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022    [BibTeX]
  @inproceedings{ Gu2022Parallel,
  title = { Parallel Cover Trees and Applications },
  author = { Gu, Yan and  Napier, Zachary and  Sun, Yihan and  Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3490148.3538581    [copy]
  Paper   Slides  
• [4] Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
  Zheqi Shen*, Zijin Wan*, Yan Gu*, and Yihan Sun*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022    [BibTeX]
  @inproceedings{ Shen2022Many,
  title = { Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient },
  author = { Shen, Zheqi and  Wan, Zijin and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3490148.3538574    [copy]
  
    Software Library:
  Parallel Dynamic Programming (DP) and greedy algorithms  [Github]
  Paper   ArXiV  Slides  
• 2020:
  [3] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
  Guy E. Blelloch, Jeremy T. Fineman, Yan Gu*, and Yihan Sun*
  
  🏆 Best Paper Candidate!
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Optimal,
  title = { Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model },
  author = { Blelloch, Guy E. and  Fineman, Jeremy T. and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3350755.3400227    [copy]
  Paper   Video  Slides  
• [2] Randomized Incremental Convex Hull is Highly Parallel
  Guy E. Blelloch, Yan Gu*, Julian Shun, and Yihan Sun*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Randomized,
  title = { Randomized Incremental Convex Hull is Highly Parallel },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3350755.3400255    [copy]
  Paper   Video  Slides  
• [1] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu*, Julian Shun, and Yihan Sun*
  
  JACM
   Journal of the ACM (JACM), 2020    [BibTeX]
  @inproceedings{ Blelloch2020Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {Journal of the ACM (JACM)},
  year = { 2020 }
  }

  [copy]
  
  
    DOI:
  10.1145/3402819    [copy]
  Paper