{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:40:25Z","timestamp":1761324025375},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662486528"},{"type":"electronic","value":"9783662486535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48653-5_34","type":"book-chapter","created":{"date-parts":[[2015,10,2]],"date-time":"2015-10-02T18:46:01Z","timestamp":1443811561000},"page":"513-527","source":"Crossref","is-referenced-by-count":10,"title":["Smoothed Analysis of Dynamic Networks"],"prefix":"10.1007","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","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":[[2015,11,5]]},"reference":[{"key":"34_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":"34_CR2","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":"34_CR3","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":"34_CR4","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":"34_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/978-3-662-45174-8_23","volume-title":"Distributed Computing","author":"O Denysyuk","year":"2014","unstructured":"Denysyuk, O., Rodrigues, L.: Random walks on evolving graphs with recurring topologies. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 333\u2013345. Springer, Heidelberg (2014)"},{"key":"34_CR6","unstructured":"Dinitz, M., Fineman, J., Gilbert, S., Newport, C.: Smoothed analysis of dynamic networks. Full version \n                    http:\/\/people.cs.georgetown.edu\/cnewport\/pubs\/SmoothingDynamicNetworks-Full.pdf"},{"key":"34_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":"34_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":"34_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"},{"issue":"1","key":"34_CR10","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":"34_CR11","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"},{"key":"34_CR12","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":"34_CR13","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":"34_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/978-3-662-45174-8_22","volume-title":"Distributed Computing","author":"C Newport","year":"2014","unstructured":"Newport, C.: Lower bounds for structuring unreliable radio networks. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 318\u2013332. Springer, Heidelberg (2014)"},{"key":"34_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-642-33651-5_10","volume-title":"Distributed Computing","author":"A Das Sarma","year":"2012","unstructured":"Das Sarma, A., Molla, A.R., Pandurangan, G.: Fast distributed computation in dynamic networks via random walks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 136\u2013150. Springer, Heidelberg (2012)"},{"issue":"3","key":"34_CR16","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":"34_CR17","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.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"issue":"10","key":"34_CR18","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. Communications of the ACM 52(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48653-5_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T23:33:45Z","timestamp":1559259225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48653-5_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662486528","9783662486535"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48653-5_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}