Publications - Graph Algorithms

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

[Back to full publication list]

  • 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  
    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  
    DOI:
    10.1145/3589259   
    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  
    DOI:
    10.1145/3572848.3577483   
    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  
    DOI:
    10.1145/3490148.3538574   
    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  
    DOI:
    10.1145/3503221.3508422   
    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  
    DOI:
    10.1145/3409964.3461782   
    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  
    DOI:
    10.1145/3402819   
    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  
    DOI:
    10.4230/LIPIcs.ICALP.2017.26   
    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  
    DOI:
    10.1145/2935764.2935765   
    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  
    DOI:
    10.1145/2935764.2935766   
    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  
    DOI:
    10.1007/978-3-662-48221-6_2   
    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  
    DOI:
    10.1145/2755573.2755597   
    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  
    DOI:
    10.1109/ICDM.2013.145   
    Influence maximization on social networks
    Paper   ArXiV  Slides