Optimizing reachability sets in temporal graphs by delaying

Deligkas, A and Potapov, I
(2022) Optimizing reachability sets in temporal graphs by delaying. .

Access the full-text of this item by clicking on the Open Access link.


A temporal graph is a dynamic graph where every edge is assigned a set of integer time labels that indicate at which discrete time step the edge is available. In this paper, we study how changes of the time labels, corresponding to delays on the availability of the edges, affect the reachability sets from given sources. We introduce control mechanisms for reachability sets that are based on two natural operations of delaying. The first operation, termed merging, is global and batches together consecutive time labels into a single time label in the whole network simultaneously. The second, imposes independent delays on the time labels of every edge of the graph. We provide a thorough investigation of the computational complexity of different objectives related to reachability sets when these operations are used.

Item Type: Conference or Workshop Item (Unspecified)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 26 May 2022 15:51
Last Modified: 21 Jun 2022 22:10
DOI: 10.1016/j.ic.2022.104890
Open Access URL: https://www.sciencedirect.com/science/article/pii/...
URI: https://livrepository.liverpool.ac.uk/id/eprint/3096397