Publications - Graph Algorithms

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

[Back to full publication list]

• 2025:
  [16] Parallel Contraction Hierarchies Can Be Efficient and Scalable (To Appear)
  Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, and Yihan Sun
  
  ICS
   International Conference on Supercomputing (ICS), 2025  [BibTeX]
  @inproceedings{ Wan2025Parallel,
  title = { Parallel Contraction Hierarchies Can Be Efficient and Scalable (To Appear) },
  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]
  
  
  parallel contraction hierarchies
  Paper   
• [15] Parallel k-Core Decomposition: Theory and Practice (To Appear)
  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 (To Appear) },
  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]
  
  
  parallel k-core
  Paper   
• [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]
  
  
  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]
  
  
  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]
  
  
  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]
  
  
  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]
  
  
  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]
  
  
  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]
  
  
  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