On Verifying and Maintaining Connectivity of Interval Temporal Networks
Abstract
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 , if it is connected for all time instances (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 ; the algorithm also considers the components of the network that start as large at time but dis-connect into small components within the time interval , and answers how long after time 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.
References
- 1. , Ephemeral networks with random availability of links: Diameter and connectivity, in SPAA (
2014 ). Google Scholar - 2. , Computation in networks of passively mobile finite-state sensors, Distributed Computing 18(4) (2006) 235–253. Crossref, ISI, Google Scholar
- 3. , How to explore a fast-changing world (cover time of a simple random walk on evolving graphs), in ICALP (
2008 ), pp. 121–132. Google Scholar - 4. , Computing shortest, fastest, and foremost journeys in dynamic networks, International Journal of Foundations of Computer Science 14(2) (2003) 267–285. Link, Google Scholar
- 5. , Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems (IJPEDS) 27(5) (2012) 387–408. Crossref, Google Scholar
- 6. , Flooding time of edge-markovian evolving graphs, SIAM Journal on Discrete Mathematics 24(4) (2010) 1694–1712. Crossref, Google Scholar
- 7. , A randomized algorithm for the joining protocol in dynamic distributed networks, Theoretical Computer Science 406(3) (2008) 248–262. Crossref, Google Scholar
- 8. , Local update algorithms for random graphs, in LATIN (
2014 ), pp. 367–378. Google Scholar - 9. , On the complexity of information spreading in dynamic networks, in SODA (
2013 ), pp. 717–736. Google Scholar - 10. , Quickest flows over time, SIAM Journal of Computing 36(6) (2007) 1600–1630. Crossref, Google Scholar
- 11. , Efficient continuous-time dynamic network flow algorithms, Operations Research Letters 23(3–5) (1998) 71–80. Crossref, Google Scholar
- 12. , Distance labeling in graphs, in SODA (
2001 ), pp. 210–219. Google Scholar - 13. , Labeling schemes for flow and connectivity, SIAM Journal on Computing 34(1) (2004) 23–40. Crossref, Google Scholar
- 14. , Connectivity and inference problems for temporal networks, in STOC (
2000 ), pp. 504–513. Crossref, Google Scholar - 15. , Continuous and discrete flows over time – A general model based on measure theory, Mathematical Methods of Operations Research 73(3) (2011) 301–337. Crossref, Google Scholar
- 16. , Distributed computation in dynamic networks, in STOC (
2010 ), pp. 513–522. Google Scholar - 17. , Temporal network optimization subject to connectivity constraints, in ICALP (
2013 ), pp. 657–668. Google Scholar - 18. , Causality, influence, and computation in possibly disconnected synchronous dynamic networks, in OPODIS (
2012 ), pp. 269–283. Google Scholar - 19. , Graph Colouring and the Probabilistic Method, Vol. 23 of
Algorithms and Combinatorics (Springer, 2002). Crossref, Google Scholar - 20. , Information dissemination in highly dynamic graphs, in DIALM-POMC (
2005 ), pp. 104–110. Google Scholar - 21. , Models and techniques for communication in dynamic networks, in STACS, Vol. 2285 of
Lecture Notes in Computer Science (2002), pp. 27–49. Crossref, Google Scholar


