Shortest Paths

[Back to full publication list]

• 2025:
  [7] Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear)
  Xiaojun Dong*, Andy Li*, Yan Gu*, and Yihan Sun*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025    [BibTeX]
  @inproceedings{ Dong2025Parallel,
  title = { Parallel Point-to-Point Shortest Paths and Batch Queries (To Appear) },
  author = { Dong, Xiaojun and  Li, Andy and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3694906.3743311    [copy]
  
    Software Library:
  Orionet: Parallel Single and Batch PPSP  [Github]
  Paper   ArXiV  Code  
• [6] 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:
  [5] Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library
  Xiaojun Dong*, Yan Gu*, Yihan Sun*, and Letong Wang*
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024    [BibTeX]
  @inproceedings{ Dong2024Brief,
  title = { Brief Announcement: PASGAL: Parallel And Scalable Graph Algorithm Library },
  author = { Dong, Xiaojun and  Gu, Yan and  Sun, Yihan and  Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2024 }
  }

  [copy]
  
  
    Software Library:
  PASGAL: Parallel And Scalable Graph Algorithm Library  [Github]
  Paper   ArXiV  Code  Slides  Poster  
• 2022:
  [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  
• 2021:
  [3] Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
  Xiaojun Dong*, Yan Gu*, Yihan Sun*, and Yunming Zhang
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021    [BibTeX]
  @inproceedings{ Dong2021Efficient,
  title = { Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths },
  author = { Dong, Xiaojun and  Gu, Yan and  Sun, Yihan and  Zhang, Yunming},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2021 }
  }

  [copy]
  
  
    DOI:
  10.1145/3409964.3461782    [copy]
  
    Software Library:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Github]
  Paper   Video  ArXiV  Code  Slides  
• [2] The Read-Only Semi-External Model
  Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu*, Charles McGuffey, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021    [BibTeX]
  @inproceedings{ Blelloch2021The,
  title = { The Read-Only Semi-External Model },
  author = { Blelloch, Guy E. and  Dhulipala, Laxman and  Gibbons, Phillip B. and  Gu, Yan and  McGuffey, Charles and  Shun, Julian},
  booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
  year = { 2021 }
  }

  [copy]
  
  Paper   
• 2020:
  [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
  
  VLDB
   International Conference on Very Large Data Bases (VLDB), 2020    [BibTeX]
  @inproceedings{ Dhulipala2020Sage:,
  title = { Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs },
  author = { Dhulipala, Laxman and  McGuffey, Charles and  Kang, Hongbo and  Gu, Yan and  Blelloch, Guy E. and  Gibbons, Phillip B. and  Shun, Julian},
  booktitle = {International Conference on Very Large Data Bases (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
    Software Library:
  SAGE: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs  [Github]
  Paper   ArXiV  Code