More Like this

1. On the Optimal Recovery of Graph Signals

   https://doi.org/10.1109/SampTA59647.2023.10301205  

   Foucart, Simon; Liao, Chunyang; Veldt, Nate (July 2023, IEEE)
2. On the tightness of graph-based statistics

   https://doi.org/10.1214/25-EJS2367  

   Chu, Lynna; Chen, Hao (January 2025, Electronic Journal of Statistics)
3. On the Semigroup of Graph Gonality Sequences

   Fessler, Austin; Jensen, David; Kelsey, Elizabeth; Owen, Noah (October 2025, The Australasian journal of combinatorics)
4. Graph Coloring on the GPU

   https://doi.org/10.1109/IPDPSW.2019.00046  

   Osama, Muhammad; Truong, Minh; Yang, Carl; Buluc, Aydin; Owens, John (May 2019, Proceedings of the Workshop on Graphs, Architectures, Programming, and Learning)

   We design and implement parallel graph coloring algorithms on the GPU using two different abstractions—one datacentric (Gunrock), the other linear-algebra-based (GraphBLAS). We analyze the impact of variations of a baseline independent-set algorithm on quality and runtime. We study how optimizations such as hashing, avoiding atomics, and a max-min heuristic affect performance. Our Gunrock graph coloring implementation has a peak 2x speed-up, a geomean speed-up of 1.3x and produces 1.6x more colors over previous hardwired state-of-theart implementations on real-world datasets. Our GraphBLAS implementation of Luby’s algorithm produces 1.9x fewer colors than the previous state-of-the-art parallel implementation at the cost of 3x extra runtime, and 1.014x fewer colors than a greedy, sequential algorithm with a geomean speed-up of 2.6x. 

   more » « less
5. Graph Coloring on the GPU

   Osama, Muhammad; Truong, Minh; Yang, Carl; Buluç, Aydın; Owens, John D. (May 2019, Proceedings of the Workshop on Graphs, Architectures, Programming, and Learning)

   We design and implement parallel graph coloring algorithms on the GPU using two different abstractions—one data-centric (Gunrock), the other linear-algebra-based (GraphBLAS). We analyze the impact of variations of a baseline independent-set algorithm on quality and runtime. We study how optimizations such as hashing, avoiding atomics, and a max-min heuristic affect performance. Our Gunrock graph coloring implementation has a peak 2x speed-up, a geomean speed-up of 1.3x and produces 1.6x more colors over previous hardwired state-of-the-art implementations on real-world datasets. Our GraphBLAS implementation of Luby's algorithm produces 1.9x fewer colors than the previous state-of-the-art parallel implementation at the cost of 3x extra runtime, and 1.014x fewer colors than a greedy, sequential algorithm with a geomean speed-up of 2.6x. 

   more » « less