On Verifying and Maintaining Connectivity of Interval Temporal Networks

Akrida, E ORCID: 0000-0002-1126-1623 and Spirakis, Paul ORCID: 0000-0001-5396-3749 (2019) On Verifying and Maintaining Connectivity of Interval Temporal Networks. Parallel Processing Letters, 29 (2). p. 1950009.

Text Interval_temporal_graphs_ppl_liverpool_elements.pdf - Author Accepted Manuscript Download (397kB) | Preview

Abstract

<jats:p> An interval temporal network is, informally speaking, a network whose links change with time. The term interval means that a link may exist for one or more time intervals, called availability intervals of the link, after which it does not exist (until, maybe, a further moment in time when it starts being available again). In this model, we consider continuous time and high-speed (instantaneous) information dissemination. An interval temporal network is connected during a period of time [Formula: see text], if it is connected for all time instances [Formula: see text] (instantaneous connectivity). In this work, we study instantaneous connectivity issues of interval temporal networks. We provide a polynomial-time algorithm that answers if a given interval temporal network is connected during a time period. If the network is not connected throughout the given time period, then we also give a polynomial-time algorithm that returns large components of the network that remain connected and remain large during [Formula: see text]; the algorithm also considers the components of the network that start as large at time [Formula: see text] but dis-connect into small components within the time interval [Formula: see text], and answers how long after time [Formula: see text] these components stay connected and large. Finally, we examine a case of interval temporal networks on tree graphs where the lifetimes of links and, thus, the failures in the connectivity of the network are not controlled by us; however, we can “feed” the network with extra edges that may re-connect it into a tree when a failure happens, so that its connectivity is maintained during a time period. We show that we can with high probability maintain the connectivity of the network for a long time period by making these extra edges available for re-connection using a randomized approach. Our approach also saves some cost in the design of availabilities of the edges; here, the cost is the sum, over all extra edges, of the length of their availability-to-reconnect interval. </jats:p>

Item Type:	Article
Uncontrolled Keywords:	Temporal graphs, temporal connectivity, time label, random input
Depositing User:	Symplectic Admin
Date Deposited:	07 Aug 2019 08:01
Last Modified:	19 Jan 2023 00:36
DOI:	10.1142/S0129626419500099
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3051119