{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:44:40Z","timestamp":1749825880581,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T00:00:00Z","timestamp":1493942400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T00:00:00Z","timestamp":1493942400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1464239","CCF-1535887"],"award-info":[{"award-number":["CCF-1464239","CCF-1535887"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1218188","CCF-1314633"],"award-info":[{"award-number":["CCF-1218188","CCF-1314633"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE Tier 2 ARC Project 2014-T2-1-157"],"award-info":[{"award-number":["MOE Tier 2 ARC Project 2014-T2-1-157"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1320279"],"award-info":[{"award-number":["CCF-1320279"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00446-017-0300-8","type":"journal-article","created":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T10:19:29Z","timestamp":1493979569000},"page":"273-287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Smoothed analysis of dynamic networks"],"prefix":"10.1007","volume":"31","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Calvin","family":"Newport","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,5]]},"reference":[{"key":"300_CR1","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 ACM-SIAM Symposium on Discrete Algorithms (2012)","DOI":"10.1137\/1.9781611973099.47"},{"key":"300_CR2","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 International Colloquium on Automata, Languages and Programming (2008)","DOI":"10.1007\/978-3-540-70575-8_11"},{"issue":"SI","key":"300_CR3","first-page":"2508","volume":"14","author":"S Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE\/ACM Trans Netw. 14(SI), 2508\u20132530 (2006)","journal-title":"IEEE\/ACM Trans Netw."},{"key":"300_CR4","doi-asserted-by":"crossref","unstructured":"Clementi, A., Silvestri, R., Trevisan, L.: Information spreading in dynamic graphs. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (2012)","DOI":"10.1145\/2332432.2332439"},{"key":"300_CR5","doi-asserted-by":"crossref","unstructured":"Cornejo, A., Gilbert, S., Newport, C.: Aggregation in dynamic networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (2012)","DOI":"10.1145\/2332432.2332468"},{"key":"300_CR6","doi-asserted-by":"crossref","unstructured":"Denysyuk, O., Rodrigues, L.: Random walks on evolving graphs with recurring topologies. In: Proceedings of the International Symposium on Distributed Computing (2014)","DOI":"10.1007\/978-3-662-45174-8_23"},{"key":"300_CR7","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 ACM-SIAM Symposium on Discrete Algorithms (2013)","DOI":"10.1137\/1.9781611973105.52"},{"key":"300_CR8","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Lynch, N., Newport, C.: The cost of radio network broadcast for different models of unreliable links. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (2013)","DOI":"10.1145\/2484239.2484259"},{"key":"300_CR9","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Karger, D.: Faster information dissemination in dynamic networks via network coding. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (2011)","DOI":"10.1145\/1993806.1993885"},{"key":"300_CR10","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proceedings of the Annual Symposium on the Foundations of Computer Science (2000)"},{"key":"300_CR11","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the Annual Symposium on the Foundations of Computer Science (2003)"},{"key":"300_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the ACM Symposium on Theory of Computing (2010)","DOI":"10.1145\/1806689.1806760"},{"issue":"1","key":"300_CR13","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/1959045.1959064","volume":"42","author":"F Kuhn","year":"2011","unstructured":"Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. ACM SIGACT News 42(1), 82\u201396 (2011)","journal-title":"ACM SIGACT News"},{"key":"300_CR14","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Oshman, R., Moses, Y.: Coordinated consensus in dynamic networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (2011)","DOI":"10.1145\/1993806.1993808"},{"key":"300_CR15","unstructured":"Lov\u00e1sz, L.: Random walks on graphs: a survey. In: Mikl\u00f3s, D., S\u00f3s, V.T., Sz\u0151nyi, T. (eds.) Combinatorics, Paul Erd\u0151s is Eighty, vol. 2, pp. 1\u201346. J\u00e1nos Bolyai Mathematical Society (1996)"},{"key":"300_CR16","doi-asserted-by":"crossref","unstructured":"Newport, C.: Lower bounds for structuring unreliable radio networks. In: Proceedings of the International Symposium on Distributed Computing (2014)","DOI":"10.1007\/978-3-662-45174-8_22"},{"key":"300_CR17","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the Workshop on Foundations of Mobile Computing (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"300_CR18","unstructured":"Sarma, A.D., Molla, A.R., Pandurangan, G.: Fast distributed computation in dynamic networks via random walks. In: Proceedings of the International Symposium on Distributed Computing (2012)"},{"issue":"3","key":"300_CR19","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"10","key":"300_CR20","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"issue":"6825","key":"300_CR21","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1038\/35065725","volume":"410","author":"SH Strogatz","year":"2001","unstructured":"Strogatz, S.H.: Exploring complex networks. Nature 410(6825), 268\u2013276 (2001)","journal-title":"Nature"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0300-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0300-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0300-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T14:59:16Z","timestamp":1589641156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0300-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,5]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["300"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0300-8","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,5,5]]},"assertion":[{"value":"1 March 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}