Department : Department Of Computer Science

Position Type : Research

A fixed-term Post-Doctoral Research Associate (PDRA) is sought, with expertise in graph algorithms and complexity, preferably also in randomized and/or approximation algorithms. The successful candidate will work at Durham University under the guidance of Dr. George Mertzios on the EPSRC-funded grant “Algorithmic Aspects of Temporal Graphs”. The research in this grant will investigate various optimization problems on temporal (i.e. dynamically changing) graphs and explore the computational complexity landscape of these new problems. More details on the grant can be found at http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/P020372/1. This project is in collaboration with Professor Paul Spirakis at the University of Liverpool. The successful candidate will be part of the Algorithms and Complexity research group (ACiD) in the Department of Computer Science at Durham. ACiD is one of the largest Algorithms and Complexity groups in the UK and it provides an excellent research environment for the proposed research.

A temporal graph consists of an underlying graph and a time-labeling function that assigns to every edge a set of discrete time-labels. These labels are drawn (in general, according to some rules) from the set of natural numbers, indicating the discrete time points where the edge is present. The conceptual shift from static to temporal graphs has a significant impact on the definition of the basic graph problems. The computational complexity of a static graph problem may or may not carry over to its temporal counterpart; this strongly depends on the problem concerned. Although some temporal graph optimization problems may be hard to solve or to approximate in the worst case, efficient algorithmic solutions may appear when the time-labeling, i.e. the pattern in which the time-labels appear, follows some stochastic rule.

Within this research we investigate the various temporal graph problems, as well as we try to more deeply understand their underlying combinatorial structure. Our over-arching goal is to develop an algorithmic temporal graph theory, similar to the algorithmic graph theory on static graphs, taking into account the inherent presence of the time dimension.

This role is Full Time and Fixed Term for 7 months.

Closes midday on : 04-Nov-2019