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
  
  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:
  Orionet: Parallel Single and Batch PPSP  [Github]
  
  parallel point-to-point shortest paths and batch queries using bidirectional search, A*, and batched bidirectional searches
  Paper   ArXiV  Code  
• [20] New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear)
  Xiangyun Ding, Yan Gu, and Yihan Sun
  
  ACDA
   SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025    [BibTeX]
  @inproceedings{ Ding2025New,
  title = { New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications (To Appear) },
  author = { Ding, Xiangyun and  Gu, Yan and  Sun, Yihan},
  booktitle = {SIAM Conference on Applied and Computational Discrete Algorithms (ACDA)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  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!
  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:
  SPoCH: Scalable Parallelization of Contraction Hierarchies  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
  
  parallel contraction hierarchies
  Paper   ArXiV  Code  Slides  
• [18] Parallel k-Core Decomposition: Theory and Practice
  Youzhe Liu, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025    [BibTeX]
  @inproceedings{ Liu2025Parallel,
  title = { Parallel k-Core Decomposition: Theory and Practice },
  author = { Liu, Youzhe and  Dong, Xiaojun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1145/3725332    [copy]
  
    Software:
  Parallel k-core implementation, integrated in PASGAL  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2025
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2025
  
  parallel k-core
  Paper   ArXiV  Code  Slides  
• [17] Parallel Cluster-BFS and Applications to Shortest Paths
  Letong Wang, Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2025    [BibTeX]
  @inproceedings{ Wang2025Parallel,
  title = { Parallel Cluster-BFS and Applications to Shortest Paths },
  author = { Wang, Letong and  Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2025 }
  }

  [copy]
  
  
    DOI:
  10.1137/1.9781611978339.4    [copy]
  
    Software:
  CBFS: Cluster Breadth-First Search  [Github]
  
  efficient implementation for parallel cluster BFS
  Paper   ArXiV  Code  Slides  
• 2024:
  [16] 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]
  
  
    DOI:
  10.1145/3626183.3660258    [copy]
  
    Software:
  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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024    [BibTeX]
  @inproceedings{ Manohar2024ParlayANN:,
  title = { ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search },
  author = { Manohar, Magdalen Dobson and  Shen, Zheqi and  , and  Dhulipala, Laxman and  Gu, Yan and  Simhadri, Harsha and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.1145/3627535.3638475    [copy]
  
    Software:
  ParlayANN: Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search  [Github]
  
  graph-based ANNS
  Paper   ArXiV  Code  
• [14] Fast and Space-Efficient Parallel Algorithms for Influence Maximization
  Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun
  
  VLDB
   Proceedings of the VLDB Endowment (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 = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2024 }
  }

  [copy]
  
  
    DOI:
  10.14778/3632093.3632104    [copy]
  
    Software:
  PaC-IM: Parallel and Compressed Influence Maximization  [Github]
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2024
  
  influence maximization
  Paper   ArXiV  Code  Poster  
• 2023:
  [13] Parallel Strong Connectivity Based on Faster Reachability
  Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2023    [BibTeX]
  @inproceedings{ Wang2023Parallel,
  title = { Parallel Strong Connectivity Based on Faster Reachability },
  author = { Wang, Letong and  Dong, Xiaojun and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3589259    [copy]
  
    Software:
  Parallel Strongly Connected Components (SCC), integrated in PASGAL  [Github]
  
  ACDA
   Poster presented at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster presented at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  
  High-performance implementation of parallel SCC
  Paper   ArXiV  Code  Slides  Poster  
• [12] Provably Fast and Space-Efficient Parallel Biconnectivity
  Xiaojun Dong, Letong Wang, Yan Gu, and Yihan Sun
  
  🏆 Best Paper Award!
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2023    [BibTeX]
  @inproceedings{ Dong2023Provably,
  title = { Provably Fast and Space-Efficient Parallel Biconnectivity },
  author = { Dong, Xiaojun and  Wang, Letong and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2023 }
  }

  [copy]
  
  
    DOI:
  10.1145/3572848.3577483    [copy]
  
    Software:
  Parallel Biconnected Components (BCC), integrated in PASGAL  [Github]
  
  ACDA
   Poster and oral presentation at the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), 2023
  
  HOPC
   Poster and oral presentation at the Highlights of Parallel Computing (HOPC@SPAA), 2023
  
  Work-, span- and space-efficient algorithm and implementation of parallel biconnected components
  Paper   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
  
  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:
  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
  
  PLDI
   ACM Conference on Programming Language Design and Implementation (PLDI), 2022    [BibTeX]
  @inproceedings{ Dhulipala2022PaC-trees:,
  title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
  author = { Dhulipala, Laxman and  Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3519939.3523733    [copy]
  
    Software:
  CPAM: Compressed Parallel Augmented Maps  [Github]
  
  Applying PaC-trees for graph streaming
  Paper   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
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022    [BibTeX]
  @inproceedings{ Anderson2022POSTER:,
  title = { POSTER: The Problem-Based Benchmark Suite (PBBS), V2 },
  author = { Anderson, Daniel and  Blelloch, Guy E. and  Dhulipala, Laxman and  Manohar, Magdalen Dobson and  Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2022 }
  }

  [copy]
  
  
    DOI:
  10.1145/3503221.3508422    [copy]
  
    Software:
  PBBS: The Problem-Based Benchmark Suite  [Github]
  
  BFS (breadth-first-search), MIS (maximal independent set), MM (maximal matching), spanning tree, minimum spanning tree
  Paper   Code  
• 2021:
  [8] 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:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Github]
  
  Parallel SSSP
  Paper   Video  ArXiV  Code  Slides  
• 2020:
  [7] 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]
  
  Parallel SCC, LE list
  Paper   
• 2017:
  [6] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017    [BibTeX]
  @inproceedings{ Blelloch2017Efficient,
  title = { Efficient Construction of Probabilistic Tree Embeddings },
  author = { Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan},
  booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
  year = { 2017 }
  }

  [copy]
  
  
    DOI:
  10.4230/LIPIcs.ICALP.2017.26    [copy]
  
  approximate SSSP, distance oracle
  Paper   ArXiV  
• 2016:
  [5] Parallel Shortest-paths Using Radius Stepping
  Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016    [BibTeX]
  @inproceedings{ Blelloch2016Parallel,
  title = { Parallel Shortest-paths Using Radius Stepping },
  author = { Blelloch, Guy E. and  Gu, Yan and  Sun, Yihan and  Tangwongsan, Kanat},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
    DOI:
  10.1145/2935764.2935765    [copy]
  
  Parallel SSSP
  Paper   
• [4] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016    [BibTeX]
  @inproceedings{ Blelloch2016Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = { Blelloch, Guy E. and  Gu, Yan and  Shun, Julian and  Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
    DOI:
  10.1145/2935764.2935766    [copy]
  
  Parallel SCC, LE list
  Paper   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
  
  WABI
   Workshop on Algorithms in Bioinformatics (WABI), 2015    [BibTeX]
  @inproceedings{ Sun2015Simultaneous,
  title = { Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE },
  author = { Sun, Yihan and  Crawford, Joseph and  Tang, Jie and  Milenkovic, Tijana},
  booktitle = {Workshop on Algorithms in Bioinformatics (WABI)},
  year = { 2015 }
  }

  [copy]
  
  
    DOI:
  10.1007/978-3-662-48221-6_2    [copy]
  
  Graph alignment algorithm for PPI network aligning
  Paper   ArXiV  
• 2014:
  [2] Fair Evaluation of Global Network Aligners
  Joseph Crawford, Yihan Sun, and Tijana Milenkovic
  
  AMB
   Algorithms for Molecular Biology (AMB), 2014    [BibTeX]
  @inproceedings{ Crawford2014Fair,
  title = { Fair Evaluation of Global Network Aligners },
  author = { Crawford, Joseph and  Sun, Yihan and  Milenkovic, Tijana},
  booktitle = {Algorithms for Molecular Biology (AMB)},
  year = { 2014 }
  }

  [copy]
  
  
    DOI:
  10.1145/2755573.2755597    [copy]
  
  Comparing graph alignment algorithms for PPI network aligning
  Paper   ArXiV  
• 2013:
  [1] Influence Maximization in Dynamic Social Networks
  Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang, and Xiaoming Sun
  
  ICDM
   IEEE International Conference on Data Mining (ICDM), 2013    [BibTeX]
  @inproceedings{ Zhuang2013Influence,
  title = { Influence Maximization in Dynamic Social Networks },
  author = { Zhuang, Honglei and  Sun, Yihan and  Tang, Jie and  Zhang, Jialin and  Sun, Xiaoming},
  booktitle = {IEEE International Conference on Data Mining (ICDM)},
  year = { 2013 }
  }

  [copy]
  
  
    DOI:
  10.1109/ICDM.2013.145    [copy]
  
  Influence maximization on social networks
  Paper   ArXiV  Slides