We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

Algorithms and Complexity for Temporal Graph Optimization and Design

KLOBAS, NINA (2024) Algorithms and Complexity for Temporal Graph Optimization and Design. Doctoral thesis, Durham University.

Available under License Creative Commons Public Domain Dedication CC0 1.0 Universal.



In this dissertation, we focus on graphs with an added time dimension, called temporal graphs.
Temporal graphs naturally model graphs whose underlying topology changes over time.
Our aim is to extend classical graph concepts with a temporal dimension and contribute to the algorithmic developments in temporal graphs.
We achieve this by presenting an in-depth study of four different problems.

We start with the problem of finding temporally disjoint paths or walks between a given set of vertices, where two paths or walks are temporally disjoint if they do not intersect at any point in time.
We focus on the special cases, where the underlying graph of the given temporal graph is either a tree or a path.
While this problem proves to be computationally demanding in general, we identify specific cases where its complexity is more manageable.

Our research extends to the Temporal Vertex Cover (TVC) and Sliding-Window Temporal Vertex Cover (Delta-TVC) problems, natural extensions of the classic Vertex Cover problem. Interestingly, Delta-TVC proves to be computationally challenging already on simple graphs like paths or cycles, presenting a sharp contrast to the more tractable TVC in similar scenarios. We introduce various algorithms to solve these problems in specific types of temporal graphs.

Shifting our focus, we explore temporal design problems for ensuring connectivity in undirected temporally connected graphs. The core objective is to minimize the number of time-labels added to the edges while preserving temporal connectivity. We present scenarios where this task is computationally challenging and others where it demonstrates more tractable behavior, which leads us to investigate the complex connection between time and structure in these graphs.

Our final problem explores temporal graph realization, specifically in constructing periodic temporal graphs with fastest paths matching prescribed time durations between vertices. We show that while this problem is generally hard, it becomes more manageable when the underlying structure resembles a tree.

Item Type:Thesis (Doctoral)
Award:Doctor of Philosophy
Keywords:Temporal graph, Graph optimization, Dynamic networks, Complexity, Algorithms, Disjoint paths, Vertex cover, Connectivity, Graph realization, Periodic temporal graph
Faculty and Department:Faculty of Science > Computer Science, Department of
Thesis Date:2024
Copyright:Copyright of this thesis is held by the author
Deposited On:24 May 2024 09:12

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter