{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:37:18Z","timestamp":1766137038785},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T00:00:00Z","timestamp":1531699200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-IDEX-03-02"],"award-info":[{"award-number":["ANR-10-IDEX-03-02"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-014"],"award-info":[{"award-number":["ANR-11-BS02-014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE25-0009-03"],"award-info":[{"award-number":["ANR-16-CE25-0009-03"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","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":[[2019,4]]},"DOI":"10.1007\/s00224-018-9876-z","type":"journal-article","created":{"date-parts":[[2018,7,15]],"date-time":"2018-07-15T22:45:05Z","timestamp":1531694705000},"page":"394-417","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Computing Parameters of Sequence-Based Dynamic Graphs"],"prefix":"10.1007","volume":"63","author":[{"given":"Arnaud","family":"Casteigts","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yessin M.","family":"Neggaz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph G.","family":"Peters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,16]]},"reference":[{"key":"9876_CR1","doi-asserted-by":"crossref","unstructured":"Aaron, E., Krizanc, D., Meyerson, E.: DMVP: Foremost waypoint coverage of time-varying graphs. In: Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014), LNCS, vol. 8747, pp 29\u201341. Springer (2014)","DOI":"10.1007\/978-3-319-12340-0_3"},{"key":"9876_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Even, S.: Efficient and reliable broadcast is achievable in an eventually connected network. In: Proceedings of the third annual ACM symposium on Principles of distributed computing (PODC), pp 278\u2013281. ACM (1984)","DOI":"10.1145\/800222.806754"},{"key":"9876_CR3","unstructured":"Barjon, M., Casteigts, A., Chaumette, S., Johnen, C., Neggaz, Y.M.: Testing temporal connectivity in sparse dynamic graphs. CoRR arXiv:\n                    1404.7634\n                    \n                  . (A French version appeared in Proceedings of ALGOTEL 2014.) (2014)"},{"key":"9876_CR4","doi-asserted-by":"crossref","unstructured":"Bondhugula, U., Devulapalli, A., Fernando, J., Wyckoff, P., Sadayappan, P.: Parallel FPGA-based all-pairs shortest-paths in a directed graph. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium. IEEE (2006)","DOI":"10.1109\/IPDPS.2006.1639347"},{"key":"9876_CR5","doi-asserted-by":"crossref","unstructured":"Bournat, M., Datta, A., Dubois, S.: Self-Stabilizing Robots in Highly Dynamic Environments. In: SSS 2016 - 18th International Symposium Stabilization, Safety, and Security of Distributed Systems, LNCS, vol. 10083, pp 54\u201369. Springer (2016)","DOI":"10.1007\/978-3-319-49259-9_5"},{"key":"9876_CR6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.ic.2016.12.004","volume":"255","author":"Q Bramas","year":"2017","unstructured":"Bramas, Q., Tixeuil, S.: The complexity of data aggregation in static and dynamic wireless sensor networks. Inf. Comput. 255, 369\u2013383 (2017)","journal-title":"Inf. Comput."},{"issue":"1","key":"9876_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.15803\/ijnc.6.1_27","volume":"6","author":"N Braud-Santoni","year":"2016","unstructured":"Braud-Santoni, N., Dubois, S., Kaaouachi, M.H., Petit, F.: The next 700 impossibility results in time-varying graphs. Int. J. Netw. Comput. 6(1), 27\u201341 (2016)","journal-title":"Int. J. Netw. Comput."},{"issue":"2","key":"9876_CR8","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B Bui-Xuan","year":"2003","unstructured":"Bui-Xuan, B., 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."},{"key":"9876_CR9","doi-asserted-by":"crossref","unstructured":"Casteigts, A., Chaumette, S., Ferreira, A.: Characterizing topological assumptions of distributed algorithms in dynamic networks. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), LNCS, vol. 5869, pp 126\u2013140. Springer (2009)","DOI":"10.1007\/978-3-642-11476-2_11"},{"issue":"2","key":"9876_CR10","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/TC.2012.208","volume":"63","author":"A Casteigts","year":"2014","unstructured":"Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. IEEE Trans. Comput. 63(2), 397\u2013410 (2014)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"9876_CR11","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1142\/S0129054115500288","volume":"26","author":"A Casteigts","year":"2015","unstructured":"Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Shortest, fastest, and foremost broadcast in dynamic networks. Int. J. Found. Comput. Sci. 26(4), 499\u2013522 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"9876_CR12","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 Emergent Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"9876_CR13","doi-asserted-by":"crossref","unstructured":"Casteigts, A., Klasing, R., Neggaz, Y.M., Peters, J.G.: Efficiently testing T-interval connectivity in dynamic graphs. In: Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015), LNCS, vol. 9079, pp 89\u2013100. Springer (2015)","DOI":"10.1007\/978-3-319-18173-8_6"},{"key":"9876_CR14","doi-asserted-by":"crossref","unstructured":"Casteigts, A., Klasing, R., Neggaz, Y.M., Peters, J.G.: A generic framework for computing parameters of sequence-based dynamic graphs. In: Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2017), LNCS, vol. 10641, pp 321\u2013338. Springer (2017)","DOI":"10.1007\/978-3-319-72050-0_19"},{"key":"9876_CR15","doi-asserted-by":"crossref","unstructured":"Dubois, S., Kaaouachi, M.H., Petit, F.: Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems. In: Symposium on Self-Stabilizing Systems, pp 51\u201366. Springer (2015)","DOI":"10.1007\/978-3-319-21741-3_4"},{"key":"9876_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2012.10.029","volume":"469","author":"P Flocchini","year":"2013","unstructured":"Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53\u201368 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9876_CR17","volume-title":"Efficient Parallel Algorithms","author":"A Gibbons","year":"1988","unstructured":"Gibbons, A., Rytter, W.: Efficient Parallel Algorithms. Cambridge University Press, Cambridge (1988)"},{"key":"9876_CR18","doi-asserted-by":"crossref","unstructured":"Godard, E., Mazauric, D.: Computing the dynamic diameter of non-deterministic dynamic networks is hard. In: Proceedings of the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2014), LNCS, vol. 8847, pp 88\u2013102. Springer (2014)","DOI":"10.1007\/978-3-662-46018-4_6"},{"key":"9876_CR19","doi-asserted-by":"crossref","unstructured":"Jain, S., Fall, K., Patra, R.: Routing in a delay tolerant network. In: Proceedings of SIGCOMM, pp 145\u2013158 (2004)","DOI":"10.1145\/1030194.1015484"},{"key":"9876_CR20","volume-title":"An Introduction to Parallel Algorithms","author":"J J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reading (1992)"},{"key":"9876_CR21","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of STOC, pp 513\u2013522. ACM (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"9876_CR22","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2013.12.024","volume":"554","author":"B Mans","year":"2014","unstructured":"Mans, B., Mathieson, L.: On the treewidth of dynamic graphs. Theor. Comput. Sci. 554, 217\u2013228 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9876_CR23","unstructured":"Neggaz, Y.M.: Automatic classification of dynamic graphs. Ph.D. thesis, University of Bordeaux. \n                    https:\/\/hal.archives-ouvertes.fr\/tel-01419691v1\n                    \n                   (2015)"},{"key":"9876_CR24","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information Dissemination in Highly Dynamic Graphs. In: Proceedings of DIALM-POMC, pp 104\u2013110. ACM (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"9876_CR25","doi-asserted-by":"crossref","unstructured":"Raynal, M., Stainer, J., Cao, J., Wu, W.: A simple broadcast algorithm for recurrent dynamic systems. In: Proceedings of the 28th IEEE International Conference on Advanced Information Networking and Applications (AINA 2014), pp 933\u2013939. IEEE (2014)","DOI":"10.1109\/AINA.2014.115"},{"issue":"2","key":"9876_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"9876_CR27","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.tcs.2015.09.030","volume":"609","author":"T Viard","year":"2016","unstructured":"Viard, T., Latapy, M., Magnien, C.: Computing maximal cliques in link streams. Theor. Comput. Sci. 609, 245\u2013252 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"9876_CR28","doi-asserted-by":"crossref","unstructured":"Whitbeck, J., Dias de Amorim, M., Conan, V., Guillaume, J.L.: Temporal reachability graphs. In: Proceedings of MOBICOM, pp 377\u2013388. ACM (2012)","DOI":"10.1145\/2348543.2348589"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9876-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9876-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9876-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T17:43:38Z","timestamp":1569001418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9876-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,16]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9876"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9876-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,16]]},"assertion":[{"value":"16 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}