Publications - Graph Algorithms

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

[Back to full publication list]

• 2023:
  [13] Parallel Strong Connectivity Based on Faster Reachability
  Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM International Conference on Management of Data (SIGMOD), 2023
  
  Theoretical and practical parallel SCC algorithms
  Conference paper  Full version (arXiv)  Code
• [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
  
  Theoretical and practical parallel biconnectivity algorithms
  Conference paper  Full version (arXiv)  Code
• 2021:
  [11] 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
  
  Theoretical and practical parallel SSSP algorithms
  Conference paper  Full version (arXiv)  Video  Code
• [10] 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, Vol. 55 Issue 1, pp. 38-46, 2021
  
  Enable parallel graph processing for geometric data
  Conference paper  Code
• [9] The Read-Only Semi-External Model
  Guy E. Blelloch, Laxman Dhulipala, Phillip B. Gibbons, Yan Gu, Charlie McGuffey, and Julian Shun
  
  APOCS
   ACM-SIAM Algorithmic Principles of Computer Systems (APoCS), 2021
  
  Traingle counting, SCC, FRT trees from graphs
  Conference paper  
• 2020:
  [8] Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
  Laxman Dhulipala, Charlie McGuffey, Hongbo Kang, Yan Gu, Guy E. Blelloch, Phillip B. Gibbons, Julian Shun
  
  🏆 Memorable Paper Award Finalist at the Non-Volatile Memories Workshop (NVMW'20)
  VLDB
   Processings of the VLDB Endowment 13(9), 2020
  
  19 commonly used graph algorithms
  Conference paper  Full version (arXiv)  Code
• [7] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM)
  
  Parallel SCC, LE-lists
  Conference paper  Journal paper  
• 2018:
  [6] Implicit Decomposition for Write-Efficient Connectivity Algorithms
  Naama Ben-David, Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
  
  IPDPS
   IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2018
  
  Graph connectivity and biconnectivity
  Conference paper  Full version (arXiv)  
• 2017:
  [5] Efficient Construction of Probabilistic Tree Embeddings
  Guy E. Blelloch, Yan Gu, and Yihan Sun
  
  ICALP
   International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
  
  approximate SSSP, distance oracle
  Conference paper  Full version (arXiv)  
• 2016:
  [4] Parallel Shortest-paths Using Radius Stepping
  Guy Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  Parallel SSSP
  Conference paper  
• [3] Parallelism in Randomized Incremental Algorithms
  Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  
  Parallel SCC, LE-lists
  Conference paper  Full version (arXiv)  
• [2] Parallel Algorithms with Asymmetric Read and Write Costs
  Naama Ben-David, Guy 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.
  
  BFS
  Conference paper  
• [1] Efficient Algorithms with Asymmetric Read and Write Costs
  Guy Blelloch, Jeremy T. Fineman, Phillip B. Gibbons Yan Gu, and Julian Shun
  
  ESA
   European Symposium on Algorithms (ESA), 2016
  
  SSSP, MST
  Conference paper  Full version (arXiv)