Publications - Graph Algorithms

You can also find my publication list on Google Scholar and DBLP.

[Back to full publication list]

• 2025:
  [18] 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]
  
  
    Software:
  Orionet: Parallel Single and Batch PPSP  [Link]
  
  parallel point-to-point shortest paths and batch queries using bidirectional search, A*, and batched bidirectional searches
  Paper   ArXiV  Code  
• [17] 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  [Link]
  
  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  
• [16] 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]
  
  
    Software:
  SPoCH: Scalable Parallelization of Contraction Hierarchies  [Link]
  
    DOI:
  10.1145/3721145.3725744    [copy]
  
  parallel contraction hierarchies
  Paper   ArXiV  Code  
• [15] 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]
  
  
    Software:
  Parallel k-core implementation, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3725332    [copy]
  
  parallel k-core
  Paper   ArXiV  Code  
• [14] Parallel Cluster-BFS and Applications to Shortest Paths
  Letong Wang, Guy 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 and Gu, Yan and Sun, Yihan},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2025 }
  }

  [copy]
  
  
    Software:
  CBFS: Cluster Breadth-First Search  [Link]
  
  efficient implementation for parallel cluster BFS
  Paper   ArXiV  Code  
• 2024:
  [13] 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:
  PASGAL: Parallel And Scalable Graph Algorithm Library  [Link]
  
  graph algorithms for strongly connected components (SCC), biconnected components (BCC), single-source shortest paths (SSSP), breadth first search (BFS)
  Paper   ArXiV  Code  Slides
• 2023:
  [12] 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]
  
  
    Software:
  Parallel SCC, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3589259    [copy]
  
  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
• [11] 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]
  
  
    Software:
  Parallel BCC, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3572848.3577483    [copy]
  
  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  Slides
• 2022:
  [10] 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]
  
  
    Software:
  Parallel DP and greedy algorithms  [Link]
  
    DOI:
  10.1145/3490148.3538574    [copy]
  
  Implementation of delta-stepping, maximal independent set, graph coloring.
  Paper   ArXiV  Slides
• [9] POSTER: The Problem-Based Benchmark Suite (PBBS), V2
  Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, 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 Dobson, Magdalen and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2022 }
  }

  [copy]
  
  
    Software:
  PBBS: The Problem-Based Benchmark Suite  [Link]
  
    DOI:
  10.1145/3503221.3508422    [copy]
  
  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]
  
  
    Software:
  Rho-Stepping: Parallel single-source shortes paths, integrated in PASGAL  [Link]
  
    DOI:
  10.1145/3409964.3461782    [copy]
  
  Parallel SSSP
  Paper   Video  ArXiV  Code  
• 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,  Zhang Jialin, 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