É«É«À²

Title of the thesis: Massively Parallel Algorithms for Sparse Graphs

Thesis defender: Rustam Latypov 
Opponent: Professor Artur Czumaj, University of Warwick, UK
Custos: Professor Jara Uitto, Aalto University School of Science

From molecular structures to social networks, many important computational problems today involve massive graphs with billions of interconnected nodes. Analysing such networks is one of the key challenges in computer science today. Processing graphs of this scale on a single machine is simply too slow. Instead, modern systems split the work across thousands of machines running in parallel. As the amount of data in the world continues to grow, efficient parallel algorithms are becoming increasingly critical for powering everyday digital life.

This thesis studies how efficiently such parallel systems can solve fundamental graph problems. The particular focus is on uniformly sparse graphs, where the number of connections is small relative to the number of nodes. Despite their apparent simplicity, sparse graphs are among the hardest cases to handle efficiently in parallel.

The research resolves several open problems and advances the state of the art by developing novel algorithms for problems such as connectivity, graph coloring, and maximal independent set. The algorithms are optimal and memory-efficient, using only as much memory as is needed to store the input itself. Taken together, the results show that even the hardest graphs can be handled efficiently in parallel, given the right algorithmic ideas.

Keywords: Massively parallel computation model, uniformly sparse graphs, connectivity, graph coloring, maximal matching, maximal independent set

Contact information:  

Thesis available for public display 7 days prior to the defence at .