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 Research Online
You are in:

On Verifying and Maintaining Connectivity of Interval Temporal Networks

Akrida, Eleni C. and Spirakis, Paul G. (2019) 'On Verifying and Maintaining Connectivity of Interval Temporal Networks.', Parallel Processing Letters, 29 (02). p. 1950009.


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 [x,y], if it is connected for all time instances t∈[x,y] (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 [x,y]; the algorithm also considers the components of the network that start as large at time t=x but dis-connect into small components within the time interval [x,y], and answers how long after time t=x 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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:Electronic version of an article published as Parallel Processing Letters, 29, 02, 2019, 1950009 © [copyright World Scientific Publishing Company]
Date accepted:09 July 2019
Date deposited:26 October 2021
Date of first online publication:23 July 2019
Date first made open access:26 October 2021

Save or Share this output

Look up in GoogleScholar