Query Algorithms for Processing Massive Graphs

Funder	Engineering and Physical Sciences Research Council
Recipient Organization	University of Bristol
Country	United Kingdom
Start Date	Sep 30, 2024
End Date	Mar 30, 2028
Duration	1,277 days
Number of Grantees	2
Roles	Student; Supervisor
Data Source	UKRI Gateway to Research
Grant ID	`2926270`

Grant Description

In this project, we will study query algorithms that execute global queries for important graph problems, including the Maximum Matching and the Maximum Independent Set problems, and the Graph Reconstruction problem, where the latter is of particular importance in the context of query algorithms.

Our general aim is to obtain algorithms with minimum query complexity and impossibility results that demonstrate that our algorithms are the best possible.