Supervisor

Suitable for

Abstract

Path queries on very large graphs ask whether node ‘b’ is reachable from node ‘a’ via certain path which is described as the path query. Problem of answering these general ‘regular’ path queries is in NP class, however with certain restrictions on the expressivity of the path queries, these queries can be tractable. The project involves finding novel ways of designing algorithms and graph processing methods for such tractable class of queries, and also find out more tractable components of such path queries. For more information please see

https://www.cs.ox.ac.uk/people/medha.atre/projects.html

Prerequisites: Knowledge of regular language, preliminary knowledge of graph algorithms.