In this SuperUROP project, we study the problem of graph connectivity and work on a fast-parallel implementation. Recent work in the graph processing community has introduced the idea of batching updates to expose greater parallelism in dynamic graph problems. This has allowed dynamic graph applications to efficiently process graphs with over a billion edges, like social networks and web graphs. We also plan to implement and benchmark an extremely efficient version of the Holm, De Lichtenberg and Thorup connectivity algorithm, that is easily usable for the community.

If there is anything amazing, it is working on something cool, and fast parallel algorithms are extremely cool 🙂