{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T20:06:20Z","timestamp":1790193980637,"version":"4.1.0"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2019,6]]},"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 \u201cfeed\u201d 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>","DOI":"10.1142\/s0129626419500099","type":"journal-article","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T04:31:23Z","timestamp":1564633883000},"page":"1950009","source":"Crossref","is-referenced-by-count":10,"title":["On Verifying and Maintaining Connectivity of Interval Temporal Networks"],"prefix":"10.1142","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1126-1623","authenticated-orcid":false,"given":"Eleni C.","family":"Akrida","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"},{"name":"Department of Computer Engineering &amp; Informatics, University of Patras, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2019,8]]},"reference":[{"key":"S0129626419500099BIB001","volume-title":"SPAA","author":"Akrida E. C."},{"key":"S0129626419500099BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"S0129626419500099BIB003","first-page":"121","volume-title":"ICALP","author":"Avin C."},{"key":"S0129626419500099BIB004","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001728"},{"key":"S0129626419500099BIB005","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"key":"S0129626419500099BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/090756053"},{"key":"S0129626419500099BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.049"},{"key":"S0129626419500099BIB008","first-page":"367","volume-title":"LATIN","author":"Duchon P."},{"key":"S0129626419500099BIB009","first-page":"717","volume-title":"SODA","author":"Dutta C."},{"key":"S0129626419500099BIB010","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427215"},{"key":"S0129626419500099BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00037-6"},{"key":"S0129626419500099BIB012","first-page":"210","volume-title":"SODA","author":"Gavoille C."},{"key":"S0129626419500099BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433912"},{"key":"S0129626419500099BIB014","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335364"},{"key":"S0129626419500099BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/s00186-011-0357-2"},{"key":"S0129626419500099BIB016","first-page":"513","volume-title":"STOC","author":"Kuhn F."},{"key":"S0129626419500099BIB017","first-page":"657","volume-title":"ICALP","author":"Mertzios G. B."},{"key":"S0129626419500099BIB018","first-page":"269","volume-title":"OPODIS","author":"Michail O."},{"key":"S0129626419500099BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"S0129626419500099BIB020","first-page":"104","volume-title":"DIALM-POMC","author":"O\u2019Dell R."},{"key":"S0129626419500099BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45841-7_2"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626419500099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T21:49:37Z","timestamp":1569361777000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626419500099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":21,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2019,8]]},"published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.1142\/S0129626419500099"],"URL":"https:\/\/doi.org\/10.1142\/s0129626419500099","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}