{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T07:00:27Z","timestamp":1779087627551,"version":"3.51.4"},"publisher-location":"Cham","reference-count":67,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319240237","type":"print"},{"value":"9783319240244","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24024-4_18","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T12:00:10Z","timestamp":1441368010000},"page":"308-343","source":"Crossref","is-referenced-by-count":34,"title":["An Introduction to Temporal Graphs: An Algorithmic Perspective"],"prefix":"10.1007","author":[{"given":"Othon","family":"Michail","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,22]]},"reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-3-319-12340-0_3","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E Aaron","year":"2014","unstructured":"Aaron, E., Krizanc, D., Meyerson, E.: DMVP: foremost waypoint coverage of time-varying graphs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 29\u201341. Springer, Heidelberg (2014)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Akrida, E.C., Gasieniec, 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), pp. 267\u2013276. ACM (2014)","DOI":"10.1145\/2612669.2612693"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"key":"18_CR4","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An $$O(\\log n\/ \\log \\log n)$$ -approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 379\u2013389. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2010). http:\/\/dl.acm.org\/citation.cfm?id=1873601.1873633"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Augustine, J., Pandurangan, G., Robinson, P., Upfal, E.: Towards robust and efficient computation in dynamic peer-to-peer networks. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 551\u2013569. SIAM (2012)","DOI":"10.1137\/1.9781611973099.47"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-540-70575-8_11","volume-title":"Automata, Languages and Programming","author":"C Avin","year":"2008","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: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121\u2013132. Springer, Heidelberg (2008)"},{"key":"18_CR7","series-title":"Efficient algorithms","volume-title":"Algorithmic Number Theory","author":"E Bach","year":"1996","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory. Efficient algorithms, vol. 1. MIT press, Cambridge (1996)"},{"issue":"3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0012-365X(72)90001-5","volume":"2","author":"B Baker","year":"1972","unstructured":"Baker, B., Shostak, R.: Gossips and telephones. Discrete Math. 2(3), 191\u2013193 (1972)","journal-title":"Discrete Math."},{"issue":"3","key":"18_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<125::AID-NET1>3.0.CO;2-P","volume":"28","author":"KA Berman","year":"1996","unstructured":"Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger\u2019s theorem. Networks 28(3), 125\u2013134 (1996)","journal-title":"Networks"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-540-39611-6_23","volume-title":"Ad-Hoc, Mobile, and Wireless Networks","author":"S Bhadra","year":"2003","unstructured":"Bhadra, S., Ferreira, A.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: Pierre, S., Barbeau, M., An, H.-C. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 259\u2013270. Springer, Heidelberg (2003)"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-540-27821-4_6","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M Bl\u00e4ser","year":"2004","unstructured":"Bl\u00e4ser, M.: A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 61\u201371. Springer, Heidelberg (2004)"},{"key":"18_CR12","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Graduate Texts in Mathematics. Springer, Heidelberg (1998). (Corrected edition, July 1, 1998)"},{"key":"18_CR13","series-title":"Cambridge Studies in Advanced Mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"issue":"2","key":"18_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.7151\/dmgt.1053","volume":"17","author":"H Broersma","year":"1997","unstructured":"Broersma, H., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory 17(2), 259\u2013269 (1997)","journal-title":"Discuss. Math. Graph Theory"},{"key":"18_CR15","first-page":"299","volume":"31","author":"H Broersma","year":"2005","unstructured":"Broersma, H., Li, X., Woeginger, G., Zhang, S.: Paths and cycles in colored graphs. Australas. J. Comb. 31, 299\u2013311 (2005)","journal-title":"Australas. J. Comb."},{"issue":"5","key":"18_CR16","doi-asserted-by":"publisher","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 Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"18_CR17","unstructured":"Clementi, A.E., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time in edge-markovian dynamic graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 213\u2013222 (2008). http:\/\/doi.acm.org\/10.1145\/1400751.1400781"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Clementi, A.E., Pasquale, F., Monti, A., Silvestri, R.: Communication in dynamic radio networks. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 205\u2013214. ACM (2007)","DOI":"10.1145\/1281100.1281131"},{"key":"18_CR19","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company, Cambridge (2001)","edition":"2"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201312. ACM (1987)","DOI":"10.1145\/41840.41841"},{"key":"18_CR21","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 Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717\u2013736. SIAM (2013)","DOI":"10.1137\/1.9781611973105.52"},{"issue":"3","key":"18_CR22","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"18_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-662-47672-7_36","volume-title":"Automata, Languages, and Programming","author":"T Erlebach","year":"2015","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 444\u2013455. Springer, Heidelberg (2015)"},{"issue":"5","key":"18_CR24","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/MNET.2004.1337732","volume":"18","author":"A Ferreira","year":"2004","unstructured":"Ferreira, A.: Building a reference combinatorial model for manets. IEEE Netw. 18(5), 24\u201329 (2004)","journal-title":"IEEE Netw."},{"issue":"3","key":"18_CR25","doi-asserted-by":"publisher","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), 71\u201380 (1998)","journal-title":"Oper. Res. Lett."},{"key":"18_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1007\/978-3-642-10631-6_55","volume-title":"Algorithms and Computation","author":"P Flocchini","year":"2009","unstructured":"Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 534\u2013543. Springer, Heidelberg (2009)"},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 550\u2013559. IEEE Computer Society, Washington, DC (2011). http:\/\/dx.doi.org\/10.1109\/FOCS.2011.80","DOI":"10.1109\/FOCS.2011.80"},{"key":"18_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-642-33651-5_12","volume-title":"Distributed Computing","author":"B Haeupler","year":"2012","unstructured":"Haeupler, B., Kuhn, F.: Lower bounds on information dissemination in dynamic networks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 166\u2013180. Springer, Heidelberg (2012)"},{"key":"18_CR29","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 160\u2013169. Society for Industrial and Applied Mathematics (1995)"},{"issue":"7","key":"18_CR30","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0895-7177(97)00050-2","volume":"25","author":"F Harary","year":"1997","unstructured":"Harary, F., Gupta, G.: Dynamic graph models. Math. Comput. Model. 25(7), 79\u201387 (1997)","journal-title":"Math. Comput. Model."},{"issue":"4","key":"18_CR31","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"SM Hedetniemi","year":"1988","unstructured":"Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks 18(4), 319\u2013349 (1988)","journal-title":"Networks"},{"issue":"3","key":"18_CR32","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal networks. Phys. Rep. 519(3), 97\u2013125 (2012)","journal-title":"Phys. Rep."},{"key":"18_CR33","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the IEEE 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 565\u2013574. IEEE (2000)"},{"key":"18_CR34","unstructured":"Karpinski, M., Schmied, R.: On improved inapproximability results for the shortest superstring and related problems. In: Proceedings of 19th CATS, pp. 27\u201336 (2013)"},{"key":"18_CR35","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.: Protocols and impossibility results for gossip-based communication mechanisms. In: Proceedings of the IEEE 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 471\u2013480. IEEE (2002)","DOI":"10.1109\/SFCS.2002.1181971"},{"key":"18_CR36","unstructured":"Kempe, D., Kleinberg, J., 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). http:\/\/doi.acm.org\/10.1145\/335305.335364"},{"key":"18_CR37","doi-asserted-by":"crossref","unstructured":"Kontogiannis, S., Michalopoulos, G., Papastavrou, G., Paraskevopoulos, A., Wagner, D., Zaroliagis, C.: Analysis and experimental evaluation of time-dependent distance oracles. In: Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 147\u2013158 (2015)","DOI":"10.1137\/1.9781611973754.13"},{"key":"18_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/978-3-662-43948-7_59","volume-title":"Automata, Languages, and Programming","author":"S Kontogiannis","year":"2014","unstructured":"Kontogiannis, S., Zaroliagis, C.: Distance oracles for time-dependent networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 713\u2013725. Springer, Heidelberg (2014)"},{"issue":"6","key":"18_CR39","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1016\/j.physa.2008.11.021","volume":"388","author":"V Kostakos","year":"2009","unstructured":"Kostakos, V.: Temporal graphs. Phys. A Stat. Mech. Appl. 388(6), 1007\u20131023 (2009)","journal-title":"Phys. A Stat. Mech. Appl."},{"issue":"2","key":"18_CR40","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(98)00034-9","volume":"66","author":"SO Krumke","year":"1998","unstructured":"Krumke, S.O., Wirth, H.C.: On the minimum label spanning tree problem. Inf. Process. Lett. 66(2), 81\u201385 (1998)","journal-title":"Inf. Process. Lett."},{"key":"18_CR41","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM symposium on Theory of Computing (STOC), pp. 513\u2013522. ACM, New York (2010). http:\/\/doi.acm.org\/10.1145\/1806689.1806760"},{"key":"18_CR42","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. SIGACT News 42, 82\u201396 (2011). http:\/\/doi.acm.org\/10.1145\/1959045.1959064 (Distributed Computing Column, Editor: Idit Keidar)","DOI":"10.1145\/1959045.1959064"},{"key":"18_CR43","volume-title":"Introduction to Parallel Algorithms and Architectures","author":"FT Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures, vol. 188. Morgan Kaufmann, San Francisco (1992)"},{"key":"18_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-642-38768-5_32","volume-title":"Computing and Combinatorics","author":"B Mans","year":"2013","unstructured":"Mans, B., Mathieson, L.: On the treewidth of dynamic graphs. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 349\u2013360. Springer, Heidelberg (2013)"},{"issue":"1","key":"18_CR45","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen kurventheorie. Fundamenta Mathematicae 10(1), 96\u2013115 (1927)","journal-title":"Fundamenta Mathematicae"},{"key":"18_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1007\/978-3-642-39212-2_57","volume-title":"Automata, Languages, and Programming","author":"GB Mertzios","year":"2013","unstructured":"Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 657\u2013668. Springer, Heidelberg (2013)"},{"key":"18_CR47","unstructured":"Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. CoRR abs\/1502.04382 (2015), full version of [MMCS13]"},{"key":"18_CR48","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $${O}(\\sqrt{|{V}|}\\cdot |{E}|)$$ algorithm for finding maximum matching in general graphs. In: Proceedings of the IEEE 21st Annual Symposium on Foundations of Computer Science (FOCS), pp. 17\u201327. IEEE (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"18_CR49","doi-asserted-by":"crossref","unstructured":"Michail, O.: Terminating distributed construction of shapes and patterns in a fair solution of automata. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC) (2015) (to appear)","DOI":"10.1145\/2767386.2767402"},{"issue":"22","key":"18_CR50","doi-asserted-by":"publisher","first-page":"2434","DOI":"10.1016\/j.tcs.2011.02.003","volume":"412","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412(22), 2434\u20132450 (2011). http:\/\/dx.doi.org\/10.1016\/j.tcs.2011.02.003","journal-title":"Theor. Comput. Sci."},{"key":"18_CR51","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New Models for Population Protocols. In: ynch, N.A. (ed.) Synthesis Lectures on Distributed Computing Theory. Morgan and Claypool (2011)","DOI":"10.2200\/S00328ED1V01Y201101DCT006"},{"key":"18_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-319-03089-0_20","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"O Michail","year":"2013","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Naming and counting in anonymous unknown dynamic networks. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 281\u2013295. Springer, Heidelberg (2013)"},{"issue":"1","key":"18_CR53","doi-asserted-by":"publisher","first-page":"2016","DOI":"10.1016\/j.jpdc.2013.07.007","volume":"74","author":"O Michail","year":"2014","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. J. Parallel Distrib. Comput. 74(1), 2016\u20132026 (2014)","journal-title":"J. Parallel Distrib. Comput."},{"key":"18_CR54","unstructured":"Michail, O., Spirakis, P.G.: Unpublished work on random temporal graphs (2012)"},{"key":"18_CR55","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. In: Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 76\u201385. ACM (2014). http:\/\/doi.acm.org\/10.1145\/2611462.2611466"},{"key":"18_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/978-3-662-44465-8_47","volume-title":"Mathematical Foundations of Computer Science 2014","author":"O Michail","year":"2014","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 553\u2013564. Springer, Heidelberg (2014)"},{"key":"18_CR57","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04016-0","volume-title":"Graph Colouring and the Probabilistic Method","author":"M Molloy","year":"2002","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method, vol. 23. Springer, Heidelberg (2002)"},{"issue":"3","key":"18_CR58","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.ipl.2005.06.009","volume":"96","author":"J Monnot","year":"2005","unstructured":"Monnot, J.: The labeled perfect matching in bipartite graphs. Inf. Process. Lett. 96(3), 81\u201388 (2005)","journal-title":"Inf. Process. Lett."},{"key":"18_CR59","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). http:\/\/doi.acm.org\/10.1145\/1080810.1080828"},{"key":"18_CR60","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: The complexity of dynamic languages and dynamic optimization problems. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC), pp. 218\u2013227. ACM (1981)","DOI":"10.1145\/800076.802475"},{"issue":"1","key":"18_CR61","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"18_CR62","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications, p. 5 (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"1","key":"18_CR63","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1137\/0147013","volume":"47","author":"B Pittel","year":"1987","unstructured":"Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213\u2013223 (1987)","journal-title":"SIAM J. Appl. Math."},{"key":"18_CR64","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: Proceedings of the IEEE 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 202\u2013213. IEEE (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"key":"18_CR65","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/3-540-45841-7_2","volume-title":"STACS 2002","author":"C Scheideler","year":"2002","unstructured":"Scheideler, C.: Models and techniques for communication in dynamic networks. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, p. 27. Springer, Heidelberg (2002)"},{"issue":"4","key":"18_CR66","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/322092.322093","volume":"25","author":"SL Tanimoto","year":"1978","unstructured":"Tanimoto, S.L., Itai, A., Rodeh, M.: Some matching problems for bipartite graphs. J. ACM 25(4), 517\u2013525 (1978)","journal-title":"J. ACM"},{"issue":"02","key":"18_CR67","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B Xuan","year":"2003","unstructured":"Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267\u2013285 (2003)","journal-title":"Int. J. Found. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms, Probability, Networks, and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24024-4_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T12:21:04Z","timestamp":1748607664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24024-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240237","9783319240244"],"references-count":67,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24024-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}