{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T06:05:42Z","timestamp":1790834742815,"version":"4.1.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,4,3]],"date-time":"2017-04-03T00:00:00Z","timestamp":1491177600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K022660\/1"],"award-info":[{"award-number":["EP\/K022660\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["FET EU IP Project MULTIPLEX under contract No. 317532"],"award-info":[{"award-number":["FET EU IP Project MULTIPLEX under contract No. 317532"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00224-017-9757-x","type":"journal-article","created":{"date-parts":[[2017,4,2]],"date-time":"2017-04-02T20:38:35Z","timestamp":1491165515000},"page":"907-944","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":36,"title":["The Complexity of Optimal Design of Temporally Connected Graphs"],"prefix":"10.1007","volume":"61","author":[{"given":"Eleni C.","family":"Akrida","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leszek","family":"G\u0105sieniec","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,4,3]]},"reference":[{"key":"9757_CR1","doi-asserted-by":"crossref","unstructured":"Akrida, E.C., G\u0105sieniec, L., Mertzios, G.B., Spirakis, P.G.: Ephemeral networks with random availability of links: diameter and connectivity. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2014)","DOI":"10.1145\/2612669.2612693"},{"key":"9757_CR2","doi-asserted-by":"crossref","unstructured":"Akrida, E.C., G\u0105sieniec, L., Mertzios, G.B., Spirakis, P.G.: On temporally connected graphs of small cost. In: Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA) (2015)","DOI":"10.1007\/978-3-319-28684-6_8"},{"key":"9757_CR3","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-319-28472-9_11","volume-title":"Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, September 17\u201318, 2015, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9536","author":"EC Akrida","year":"2015","unstructured":"Akrida, E.C., Spirakis, P.G.: On verifying and maintaining connectivity of interval temporal networks. In: Bose, P., Gasieniec, L.A., R\u00f6mer, K., Wattenhofer, R. (eds.) Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, September 17\u201318, 2015, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9536, pp 142\u2013154. Springer, Patras, Greece (2015). doi: 10.1007\/978-3-319-28472-9_11"},{"key":"9757_CR4","first-page":"288","volume-title":"Proceedings of the Third Italian Conference on Algorithms and Complexity, CIAC \u201997","author":"P Alimonti","year":"1997","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Proceedings of the Third Italian Conference on Algorithms and Complexity, CIAC \u201997, pp 288\u2013298. Springer, London, UK (1997). http:\/\/dl.acm.org\/citation.cfm?id=648256.752884"},{"key":"9757_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput., 235\u2013253 (2006)","DOI":"10.1007\/s00446-005-0138-3"},{"key":"9757_CR6","doi-asserted-by":"crossref","unstructured":"Avin, C., Kouck\u00fd, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp. 121\u2013132 (2008)","DOI":"10.1007\/978-3-540-70575-8_11"},{"key":"9757_CR7","unstructured":"Barjon, M., Casteigts, A., Chaumette, S., Johnen, C., Neggaz, Y.M.: Testing Temporal Connectivity in Sparse Dynamic Graphs. arXiv: 1404.7634 (2014)"},{"key":"9757_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs, 2nd edn","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)"},{"issue":"2","key":"9757_CR9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"BM Bui-Xuan","year":"2003","unstructured":"Bui-Xuan, B.M., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267\u2013285 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"9757_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. (IJPEDS) 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst. (IJPEDS)"},{"key":"9757_CR11","doi-asserted-by":"publisher","unstructured":"Chaintreau, A., Mtibaa, A., Massouli\u00e9, L., Diot, C.: The diameter of opportunistic mobile networks. In: Kurose, J., Schulzrinne, H. (eds.) Proceedings of the 2007 ACM Conference on Emerging Network Experiment and Technology, CoNEXT 2007, New York, NY, USA, December 10\u201313, 2007, p. 12. ACM (2007). doi: 10.1145\/1364654.1364670","DOI":"10.1145\/1364654.1364670"},{"issue":"4","key":"9757_CR12","doi-asserted-by":"crossref","first-page":"1694","DOI":"10.1137\/090756053","volume":"24","author":"AEF Clementi","year":"2010","unstructured":"Clementi, A.E.F., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time of edge-markovian evolving graphs. SIAM J. Discret. Math. (SIDMA) 24(4), 1694\u20131712 (2010)","journal-title":"SIAM J. Discret. Math. (SIDMA)"},{"key":"9757_CR13","doi-asserted-by":"crossref","unstructured":"Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z., Viola, E.: On the complexity of information spreading in dynamic networks. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717\u2013736 (2013)","DOI":"10.1137\/1.9781611973105.52"},{"issue":"6","key":"9757_CR14","doi-asserted-by":"publisher","first-page":"1600","DOI":"10.1137\/S0097539703427215","volume":"36","author":"L Fleischer","year":"2007","unstructured":"Fleischer, L., Skutella, M.: Quickest flows over time. SIAM J. Comput. 36(6), 1600\u20131630 (2007). doi: 10.1137\/S0097539703427215","journal-title":"SIAM J. Comput."},{"issue":"3-5","key":"9757_CR15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0167-6377(98)00037-6","volume":"23","author":"L Fleischer","year":"1998","unstructured":"Fleischer, L., Tardos, \u00c9.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3-5), 71\u201380 (1998)","journal-title":"Oper. Res. Lett."},{"key":"9757_CR16","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 210\u2013219 (2001)"},{"issue":"6","key":"9757_CR17","doi-asserted-by":"publisher","first-page":"1649","DOI":"10.1137\/09076725X","volume":"41","author":"A Gupta","year":"2012","unstructured":"Gupta, A., Krishnaswamy, R., Ravi, R.: Online and stochastic survivable network design. SIAM J. Comput. 41(6), 1649\u20131672 (2012). doi: 10.1137\/09076725X","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9757_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"9757_CR19","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 504\u2013513 (2000)","DOI":"10.1145\/335305.335364"},{"issue":"4-5","key":"9757_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0167-6377(98)00009-1","volume":"22","author":"B Klinz","year":"1998","unstructured":"Klinz, B., Woeginger, G.J.: One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs. Oper. Res. Lett. 22(4-5), 119\u2013127 (1998). doi: 10.1016\/S0167-6377(98)00009-1","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9757_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00186-011-0357-2","volume":"73","author":"R Koch","year":"2011","unstructured":"Koch, R., Nasrabadi, E., Skutella, M.: Continuous and discrete flows over time - a general model based on measure theory. Math. Meth. OR 73(3), 301\u2013337 (2011). doi: 10.1007\/s00186-011-0357-2","journal-title":"Math. Meth. OR"},{"key":"9757_CR22","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"issue":"3","key":"9757_CR23","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1137\/070700620","volume":"39","author":"LC Lau","year":"2009","unstructured":"Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062\u20131087 (2009). doi: 10.1137\/070700620","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9757_CR24","doi-asserted-by":"publisher","first-page":"2217","DOI":"10.1137\/110854461","volume":"42","author":"LC Lau","year":"2013","unstructured":"Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. SIAM J. Comput. 42(6), 2217\u20132242 (2013). doi: 10.1137\/110854461","journal-title":"SIAM J. Comput."},{"key":"9757_CR25","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Part II, pp. 657\u2013668 (2013)","DOI":"10.1007\/978-3-642-39212-2_57"},{"key":"9757_CR26","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory Morgan & Claypool Publishers (2011)","DOI":"10.2200\/S00328ED1V01Y201101DCT006"},{"key":"9757_CR27","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks OPODIS, pp. 269\u2013283 (2012)","DOI":"10.1007\/978-3-642-35476-2_19"},{"key":"9757_CR28","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005). https:\/\/books.google.co.uk\/books?id=0bAYl6d7hvkC","DOI":"10.1017\/CBO9780511813603"},{"key":"9757_CR29","doi-asserted-by":"crossref","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, vol. 23. Springer (2002)","DOI":"10.1007\/978-3-642-04016-0"},{"key":"9757_CR30","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"issue":"3","key":"9757_CR31","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991). doi: 10.1016\/0022-0000(91)90023-X","journal-title":"J. Comput. Syst. Sci."},{"key":"9757_CR32","doi-asserted-by":"crossref","unstructured":"Scheideler, C.: Models and techniques for communication in dynamic networks. In: Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 2285, pp. 27\u201349 (2002)","DOI":"10.1007\/3-540-45841-7_2"},{"key":"9757_CR33","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/2348543.2348589","volume-title":"Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Mobicom \u201912","author":"J Whitbeck","year":"2012","unstructured":"Whitbeck, J., Dias de Amorim, M., Conan, V., Guillaume, J.L.: Temporal reachability graphs. In: Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Mobicom \u201912, pp 377\u2013388. ACM, New York, NY, USA (2012). doi: 10.1145\/2348543.2348589"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9757-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9757-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9757-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T10:31:09Z","timestamp":1568975469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9757-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,3]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9757"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9757-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,3]]}}}