World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

On Verifying and Maintaining Connectivity of Interval Temporal Networks

    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.

    References

    • 1. E. C. Akrida et al., Ephemeral networks with random availability of links: Diameter and connectivity, in SPAA (2014). Google Scholar
    • 2. D. Angluin et al., Computation in networks of passively mobile finite-state sensors, Distributed Computing 18(4) (2006) 235–253. Crossref, ISIGoogle Scholar
    • 3. C. Avin, M. Koucký and Z. Lotker, 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. B.-M. Bui-Xuan, A. Ferreira and A. Jarry, Computing shortest, fastest, and foremost journeys in dynamic networks, International Journal of Foundations of Computer Science 14(2) (2003) 267–285. LinkGoogle Scholar
    • 5. A. Casteigts et al., Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems (IJPEDS) 27(5) (2012) 387–408. CrossrefGoogle Scholar
    • 6. A. E. F. Clementi et al., Flooding time of edge-markovian evolving graphs, SIAM Journal on Discrete Mathematics 24(4) (2010) 1694–1712. CrossrefGoogle Scholar
    • 7. C. Cooper, R. Klasing and T. Radzik, A randomized algorithm for the joining protocol in dynamic distributed networks, Theoretical Computer Science 406(3) (2008) 248–262. CrossrefGoogle Scholar
    • 8. P. Duchon and R. Duvignau, Local update algorithms for random graphs, in LATIN (2014), pp. 367–378. Google Scholar
    • 9. C. Dutta et al., On the complexity of information spreading in dynamic networks, in SODA (2013), pp. 717–736. Google Scholar
    • 10. L. Fleischer and M. Skutella, Quickest flows over time, SIAM Journal of Computing 36(6) (2007) 1600–1630. CrossrefGoogle Scholar
    • 11. L. Fleischer and É. Tardos, Efficient continuous-time dynamic network flow algorithms, Operations Research Letters 23(3–5) (1998) 71–80. CrossrefGoogle Scholar
    • 12. C. Gavoille et al., Distance labeling in graphs, in SODA (2001), pp. 210–219. Google Scholar
    • 13. M. Katz et al., Labeling schemes for flow and connectivity, SIAM Journal on Computing 34(1) (2004) 23–40. CrossrefGoogle Scholar
    • 14. D. Kempe, J. M. Kleinberg and A. Kumar, Connectivity and inference problems for temporal networks, in STOC (2000), pp. 504–513. CrossrefGoogle Scholar
    • 15. R. Koch, E. Nasrabadi and M. Skutella, Continuous and discrete flows over time – A general model based on measure theory, Mathematical Methods of Operations Research 73(3) (2011) 301–337. CrossrefGoogle Scholar
    • 16. F. Kuhn, N. A. Lynch and R. Oshman, Distributed computation in dynamic networks, in STOC (2010), pp. 513–522. Google Scholar
    • 17. G. B. Mertzios et al., Temporal network optimization subject to connectivity constraints, in ICALP (2013), pp. 657–668. Google Scholar
    • 18. O. Michail, I. Chatzigiannakis and P. G. Spirakis, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, in OPODIS (2012), pp. 269–283. Google Scholar
    • 19. M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method, Vol. 23 of Algorithms and Combinatorics (Springer, 2002). CrossrefGoogle Scholar
    • 20. R. O’Dell and R. Wattenhofer, Information dissemination in highly dynamic graphs, in DIALM-POMC (2005), pp. 104–110. Google Scholar
    • 21. C. Scheideler, Models and techniques for communication in dynamic networks, in STACS, Vol. 2285 of Lecture Notes in Computer Science (2002), pp. 27–49. CrossrefGoogle Scholar