{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T23:58:48Z","timestamp":1773187128870,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642404498","type":"print"},{"value":"9783642404504","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_28","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"325-336","source":"Crossref","is-referenced-by-count":12,"title":["Rumor Spreading in Random Evolving Graphs"],"prefix":"10.1007","author":[{"given":"Andrea","family":"Clementi","sequence":"first","affiliation":[]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[]},{"given":"Carola","family":"Doerr","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Isopi","sequence":"additional","affiliation":[]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[]},{"given":"Francesco","family":"Pasquale","sequence":"additional","affiliation":[]},{"given":"Riccardo","family":"Silvestri","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","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.\u00a05125, pp. 121\u2013132. Springer, Heidelberg (2008)"},{"issue":"1","key":"28_CR2","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM J. on Computing\u00a029(1), 180\u2013200 (1999)","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00446-011-0133-9","volume":"24","author":"H. Baumann","year":"2011","unstructured":"Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. Distributed Computing\u00a024(1), 31\u201344 (2011)","journal-title":"Distributed Computing"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511814068"},{"key":"28_CR5","unstructured":"Boyd, S., Arpita, G., Balaji, P., Devavrat, S.: Gossip algorithms: Design, analysis and applications. In: Proc. of 24th INFOCOM, pp. 1653\u20131664. IEEE (2005)"},{"key":"28_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-642-02930-1_31","volume-title":"Automata, Languages and Programming","author":"F. Chierichetti","year":"2009","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumor Spreading in Social Networks. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 375\u2013386. Springer, Heidelberg (2009)"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds on rumour spreading by conductance. In: Proc. of 42nd ACM STOC, pp. 399\u2013408 (2010)","DOI":"10.1145\/1806689.1806745"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumour spreading and graph conductance. In: Proc. of 21th ACM-SIAM SODA, pp. 1657\u20131663 (2010)","DOI":"10.1137\/1.9781611973075.135"},{"key":"28_CR9","unstructured":"Clementi, A., Crescenzi, P., Doerr, C., Fraigniaud, P., Isopi, M., Pasquale, F., Panconesi, A., Silvestri, R.: Rumor Spreading in Random Evolving Graphs, \n                  \n                    http:\/\/arxiv.org\/abs\/1302.3828"},{"issue":"4","key":"28_CR10","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1137\/090756053","volume":"24","author":"A. Clementi","year":"2010","unstructured":"Clementi, A., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time of edge-Markovian evolving graphs. SIAM J. Discrete Math.\u00a024(4), 1694\u20131712 (2010)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"28_CR11","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.jcss.2008.10.004","volume":"75","author":"A. Clementi","year":"2009","unstructured":"Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Broadcasting in dynamic radio networks. J. Comput. Syst. Sci.\u00a075(4), 213\u2013230 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"9","key":"28_CR12","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1109\/TPDS.2011.33","volume":"22","author":"A. Clementi","year":"2011","unstructured":"Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Information spreading in stationary Markovian evolving graph. IEEE Trans. Parallel Distrib. Syst.\u00a022(9), 1425\u20131432 (2011)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"28_CR13","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: Proc. of 6th ACM PODC, pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"key":"28_CR14","first-page":"21","volume-title":"Proc. of 43rd ACM STOC","author":"B. Doerr","year":"2011","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. In: Proc. of 43rd ACM STOC, pp. 21\u201330. ACM, New York (2011)"},{"issue":"6","key":"28_CR15","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1016\/j.dam.2012.10.014","volume":"161","author":"B. Doerr","year":"2013","unstructured":"Doerr, B., Huber, A., Levavi Strong, A.: robustness of randomized rumor spreading protocols. Discrete Applied Mathematics\u00a0161(6), 778\u2013793 (2013)","journal-title":"Discrete Applied Mathematics"},{"key":"28_CR16","first-page":"290","volume":"6","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On Random Graphs. Publ. Math.\u00a06, 290\u2013297 (1959)","journal-title":"Publ. Math."},{"issue":"4","key":"28_CR17","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U. Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Structures and Algorithms\u00a01(4), 447\u2013460 (1990)","journal-title":"Random Structures and Algorithms"},{"key":"28_CR18","unstructured":"Ferreira, A.: On models and algorithms for dynamic communication networks: The case for evolving graphs. In: Proc. of 4th ALGOTEL, pp. 155\u2013161 (2002)"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Huber, A., Panagiotou, K.: Reliable broadcasting in random networks and the effect of density. In: Proc. of 29th IEEE INFOCOM, pp. 2552\u20132560 (2010)","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"28_CR20","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K.: Rumor spreading on random regular graphs and expanders. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 560\u2013573. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15369-3_42"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: Proc. of 23rd ACM-SIAM SODA, pp. 1642\u20131660 (2012)","DOI":"10.1137\/1.9781611973099.130"},{"issue":"1","key":"28_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A. Frieze","year":"1985","unstructured":"Frieze, A., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics\u00a010(1), 57\u201377 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"28_CR23","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: Proc. of 28th STACS. LIPIcs, vol.\u00a09, pp. 57\u201368. Schloss Dagstuhl (2011)"},{"key":"28_CR24","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Sauerwald, T.: Rumor spreading and vertex expansion. In: Proc. of 23rd ACM-SIAM SODA, pp. 1623\u20131641. SIAM (2012)","DOI":"10.1137\/1.9781611973099.129"},{"issue":"4","key":"28_CR25","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","volume":"30","author":"E.N. Gilbert","year":"1959","unstructured":"Gilbert, E.N.: Random graphs. Annals of Math. Statistics\u00a030(4), 1141\u20131144 (1959)","journal-title":"Annals of Math. Statistics"},{"issue":"2115","key":"28_CR26","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1098\/rspa.2009.0456","volume":"466","author":"P. Grindrod","year":"2010","unstructured":"Grindrod, P., Higham, D.J.: Evolving graphs: dynamical models, inverse problems and propagation. Proc. R. Soc. A\u00a0466(2115), 753\u2013770 (2010)","journal-title":"Proc. R. Soc. A"},{"key":"28_CR27","first-page":"229","volume-title":"Proc. of 18th PODC","author":"M. Harchol-Balter","year":"1999","unstructured":"Harchol-Balter, M., Leighton, T., Lewin, D.: Resource discovery in distributed networks. In: Proc. of 18th PODC, pp. 229\u2013237. ACM, New York (1999)"},{"key":"28_CR28","doi-asserted-by":"publisher","first-page":"5001","DOI":"10.1109\/TIT.2010.2059830","volume":"56","author":"P. Jacquet","year":"2010","unstructured":"Jacquet, P., Mans, B., Rodolakis, G.: Information Propagation Speed in Mobile and Delay Tolerant Networks. IEEE Trans. on Inf. Theory\u00a056, 5001\u20135015 (2010)","journal-title":"IEEE Trans. on Inf. Theory"},{"issue":"3","key":"28_CR29","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/1275517.1275520","volume":"25","author":"M. Jelasity","year":"2007","unstructured":"Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., van Steen, M.: Gossip-based Peer Sampling. ACM Trans. Comp. Syst.\u00a025(3), Article 8 (2007)","journal-title":"ACM Trans. Comp. Syst."},{"key":"28_CR30","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proc. of 41st IEEE FOCS, pp. 565\u2013574. IEEE (2000)"},{"issue":"5","key":"28_CR31","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1317379.1317381","volume":"41","author":"A.-M. Kermarrec","year":"2007","unstructured":"Kermarrec, A.-M., van Steen, M.: Gossiping in distributed systems. SIGOPS Oper. Syst. Rev.\u00a041(5), 2\u20137 (2007)","journal-title":"SIGOPS Oper. Syst. Rev."},{"key":"28_CR32","first-page":"513","volume-title":"Proc. of 42nd ACM STOC","author":"F. Kuhn","year":"2010","unstructured":"Kuhn, F., Linch, N., Oshman, R.: Distributed Computation in Dynamic Networks. In: Proc. of 42nd ACM STOC, pp. 513\u2013522. ACM, New York (2010)"},{"issue":"1","key":"28_CR33","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\u00a042(1), 82\u201396 (2011)","journal-title":"ACM SIGACT News"},{"issue":"1","key":"28_CR34","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 Journal on Applied Mathematics\u00a047(1), 213\u2013223 (1987)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"28_CR35","doi-asserted-by":"crossref","unstructured":"Sauerwald, T., Stauffer, A.: Rumor spreading and vertex expansion on regular graphs. In: Proc. of 22nd ACM-SIAM SODA, pp. 462\u2013475. SIAM (2011)","DOI":"10.1137\/1.9781611973082.37"},{"key":"28_CR36","doi-asserted-by":"crossref","unstructured":"Van Renesse, R., Minsky, Y., Hayden, M.: A Gossip-Style Failure Detection Service. In: Proc. of Middleware, pp. 55\u201370 (1998)","DOI":"10.1007\/978-1-4471-1283-9_4"},{"key":"28_CR37","doi-asserted-by":"crossref","unstructured":"Vojnovic, M., Proutier, A.: Hop limited flooding over dynamic networks. In: Proc. of 30th IEEE INFOCOM, pp. 685\u2013693. IEEE (2011)","DOI":"10.1109\/INFCOM.2011.5935249"},{"issue":"5","key":"28_CR38","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1109\/TCOMM.2011.020811.090163","volume":"59","author":"J. Whitbeck","year":"2011","unstructured":"Whitbeck, J., Conan, V., de Amorim, M.D.: Performance of Opportunistic Epidemic Routing on Edge-Markovian Dynamic Graphs. IEEE Transactions on Communications\u00a059(5), 1259\u20131263 (2011)","journal-title":"IEEE Transactions on Communications"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:51:34Z","timestamp":1558302694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}