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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (389Kb)
|Publisher Web site:||https://doi.org/10.1142/S0129626419500099|
|Publisher statement:||Electronic version of an article published as Parallel Processing Letters, 29, 02, 2019, 1950009 https://doi.org/10.1142/S0129626419500099 © [copyright World Scientific Publishing Company] http://www.worldscientific.com/worldscinet/ppl|
|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|