Optimizing reachability sets in temporal graphs by delaying



Deligkas, Argyrios and Potapov, Igor
(2022) Optimizing reachability sets in temporal graphs by delaying. INFORMATION AND COMPUTATION, 285. pp. 9810-9817.

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

Abstract

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: Article
Uncontrolled Keywords: Temporal graphs, Reachability sets, Optimization, NP-hard
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: 16 Jan 2024 10:14
DOI: 10.1016/j.ic.2022.104890
Open Access URL: https://www.sciencedirect.com/science/article/pii/...
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3096397