[Back to full publication list]

• 2025:
  [21] 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{ cluster-bfs,
  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:
  [20] 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{ pasgal,
  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  
• [19] ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search
  Magdalen Dobson, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Simhadri, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2024    [BibTeX]
  @inproceedings{ ann,
  title = { ParlayANN: Scalable and Deterministic Parallel Graph-Based Algorithms for Approximate Nearest Neighbor Search },
  author = {Dobson, Magdalen and Shen, Zheqi and Blelloch, Guy 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]
  
  
  graph-based ANNS
  Paper   ArXiV  Code  
• 2023:
  [18] 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{ scc,
  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]
  
  
  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  
• [17] 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{ bcc,
  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]
  
  
  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  
• 2022:
  [16] 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{ iterative,
  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]
  
  
  Implementation of delta-stepping, maximal independent set, graph coloring.
  Paper   ArXiV  Slides  
• [15] 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{ pbbsv2,
  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]
  
  
  BFS (breadth-first-search), MIS (maximal independent set), MM (maximal matching), spanning tree, minimum spanning tree
  Paper   Code  
• 2021:
  [14] 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{ stepping,
  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]
  
  
  Parallel SSSP
  Paper   Video  ArXiV  Code  
• [13] GeoGraph: A Framework for Graph Processing on Geometric Data
  Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun
  
  SIGOPS-OSR
   ACM SIGOPS Operating Systems Review (SIGOPS-OSR), 2021    [BibTeX]
  @inproceedings{ geograph,
  title = { GeoGraph: A Framework for Graph Processing on Geometric Data },
  author = {Wang, Yiqiu and Yu, Shangdi and Dhulipala, Laxman and Gu, Yan and Shun, Julian},
  booktitle = {ACM SIGOPS Operating Systems Review (SIGOPS-OSR)},
  year = { 2021 }
  }

  [copy]
  
  
  Enable parallel graph processing for geometric data
  Paper   Code  
• [12] 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{ ,
  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]
  
  
  Traingle counting, SCC, FRT trees from graphs
  Paper   
• 2020:
  [11] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM), 2020    [BibTeX]
  @inproceedings{ incremental-jacm,
  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]
  
  
  Parallel SCC, LE list
  Paper   
• [10] 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
   Proceedings of the VLDB Endowment (VLDB), 2020    [BibTeX]
  @inproceedings{ ,
  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 = {Proceedings of the VLDB Endowment (VLDB)},
  year = { 2020 }
  }

  [copy]
  
  
  19 commonly used graph algorithms
  Paper   ArXiV  Code  
• 2018:
  [9] Implicit Decomposition for Write-Efficient Connectivity Algorithms
  Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  IPDPS
   IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018    [BibTeX]
  @inproceedings{ decomposition,
  title = { Implicit Decomposition for Write-Efficient Connectivity Algorithms },
  author = {Ben-David, Naama and Blelloch, Guy E. and Fineman, Jeremy T. and Gibbons, Phillip B. and Gu, Yan and McGuffey, Charles and Shun, Julian},
  booktitle = {IEEE International Parallel & Distributed Processing Symposium (IPDPS)},
  year = { 2018 }
  }

  [copy]
  
  
  Graph connectivity and biconnectivity
  Paper   ArXiV  
• 2017:
  [8] 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{ frt,
  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]
  
  
  approximate SSSP, distance oracle
  Paper   ArXiV  
• 2016:
  [7] 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{ radius-stepping,
  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]
  
  
  Parallel SSSP
  Paper   
• [6] 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{ incremental,
  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]
  
  
  Parallel SCC, LE list
  Paper   ArXiV  
• [5] Parallel Algorithms with Asymmetric Read and Write Costs
  Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016    [BibTeX]
  @inproceedings{ ,
  title = { Parallel Algorithms with Asymmetric Read and Write Costs },
  author = {Ben-David, Naama and Blelloch, Guy E. and Fineman, Jeremy T. and Gibbons, Phillip B. and Gu, Yan and McGuffey, Charles and Shun, Julian},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
  BFS
  Paper   
• [4] Efficient Algorithms with Asymmetric Read and Write Costs
  Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  ESA
   European Symposium on Algorithms (ESA), 2016    [BibTeX]
  @inproceedings{ ,
  title = { Efficient Algorithms with Asymmetric Read and Write Costs },
  author = {Blelloch, Guy E. and Fineman, Jeremy T. and Gibbons, Phillip B. and Gu, Yan and McGuffey, Charles and Shun, Julian},
  booktitle = {European Symposium on Algorithms (ESA)},
  year = { 2016 }
  }

  [copy]
  
  
  SSSP, MST
  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{ wave,
  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]
  
  
  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{ ppi-exp,
  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]
  
  
  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{ dynamicinf,
  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]
  
  
  Influence maximization on social networks
  Paper   ArXiV  Slides