Graph Coloring

[Back to full publication list]

Parallel algorithms and implementations for graph coloring

2022:
[3] 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 }
}

  DOI:
10.1145/3490148.3538574
  Software Library:
Parallel Dynamic Programming (DP) and greedy algorithms  [Github]
Paper   ArXiV  Slides
2021:
[2] 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{ Blelloch2021The,
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 }
}

Paper
2020:
[1] 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
International Conference on Very Large Data Bases (VLDB), 2020    [BibTeX]

@inproceedings{ Dhulipala2020Sage:,
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 = {International Conference on Very Large Data Bases (VLDB)},
year = { 2020 }
}

  Software Library:
SAGE: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs  [Github]
Paper   ArXiV  Code