Publications - Graph Algorithms

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

[Back to full publication list]

• 2023:
  [12] Parallel Strong Connectivity Based on Faster Reachability (To Appear)
  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 (To Appear) },
  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]
  
  
  High-performance implementation of parallel SCC
  Paper   
• [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{ 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]
  
  
  Work-, span- and space-efficient algorithm and implementation of parallel biconnected components
  Paper   ArXiV  Code  
• 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{ 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
• [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{ 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:
  [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{ 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  
• 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{ 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   
• 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{ 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:
  [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{ 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   
• [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{ 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  
• 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