{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T15:27:05Z","timestamp":1759937225345},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_42","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"560-573","source":"Crossref","is-referenced-by-count":21,"title":["Rumor Spreading on Random Regular Graphs and Expanders"],"prefix":"10.1007","author":[{"given":"Nikolaos","family":"Fountoulakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","volume":"24","author":"E.A. Bender","year":"1978","unstructured":"Bender, E.A., Canfield, E.R.: The asymptotic number of labelled graphs with given degree sequences. J. Combin. Theory Ser. A\u00a024, 296\u2013307 (1978)","journal-title":"J. Combin. Theory Ser. A"},{"key":"42_CR2","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B. Bollob\u00e1s","year":"1980","unstructured":"Bollob\u00e1s, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin.\u00a01, 311\u2013316 (1980)","journal-title":"Europ. J. Combin."},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Bradonjic, M., Els\u00e4sser, R., Friedrich, T., Sauerwald, T., Stauffer, A.: Efficient broadcast on random geometric graphs. In: SODA 2010, pp. 1412\u20131421 (2010)","DOI":"10.1137\/1.9781611973075.114"},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost Tight Bounds for Rumour Spreading with Conductance. In: STOC 2010, pp. 399\u2013408 (2010)","DOI":"10.1145\/1806689.1806745"},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02125347","volume":"9","author":"F.R.K. Chung","year":"1989","unstructured":"Chung, F.R.K., Graham, R., Wilson, R.M.: Quasi-random graphs. Combinatorica\u00a09, 345\u2013362 (1989)","journal-title":"Combinatorica"},{"key":"42_CR6","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: PODC 1987, pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"key":"42_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"42_CR8","volume-title":"Random Graph Dynamics","author":"R. Durrett","year":"2007","unstructured":"Durrett, R.: Random Graph Dynamics. Cambridge University Press, New York (2007)"},{"key":"42_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/11864219_26","volume-title":"Distributed Computing","author":"R. Els\u00e4sser","year":"2006","unstructured":"Els\u00e4sser, R.: On randomized broadcasting in power law networks. In: Dolev, S. (ed.) DISC 2006. LNCS, vol.\u00a04167, pp. 370\u2013384. Springer, Heidelberg (2006)"},{"key":"42_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-540-87779-0_15","volume-title":"Distributed Computing","author":"R. Els\u00e4sser","year":"2008","unstructured":"Els\u00e4sser, R., Gasieniec, L., Sauerwald, T.: On radio broadcasting in random geometric graphs. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 212\u2013226. Springer, Heidelberg (2008)"},{"key":"42_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-70918-3_15","volume-title":"STACS 2007","author":"R. Els\u00e4sser","year":"2007","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On Broadcasting vs. mixing and information dissemination on Caley graphs. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 163\u2013174. Springer, Heidelberg (2007)"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1016\/j.tcs.2008.04.017","volume":"410","author":"R. Els\u00e4sser","year":"2009","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. Theoretical Computer Science\u00a0410, 3414\u20133427 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"42_CR13","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":"42_CR14","doi-asserted-by":"crossref","unstructured":"Fountoulakis, N., Huber, A., Panagiotou, K.: Reliable broadcasting and the effect of density. In: IEEE INFOCOM 2010, pp. TS58 (2010)","DOI":"10.1109\/INFCOM.2010.5462084"},{"key":"42_CR15","unstructured":"Fountoulakis, N., Panagiotou, K.: Rumor spreading on random regular graphs and expanders, full version, http:\/\/arxiv.org\/abs\/1002.3518"},{"key":"42_CR16","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1215\/S0012-7094-93-06921-9","volume":"69","author":"J. Friedman","year":"1993","unstructured":"Friedman, J.: Some geometric aspects of graphs and their eigenfunctions. Duke Math. J.\u00a069, 487\u2013525 (1993)","journal-title":"Duke Math. J."},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A.M. Frieze","year":"1985","unstructured":"Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math.\u00a010, 57\u201377 (1985)","journal-title":"Discrete Appl. Math."},{"key":"42_CR18","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. AMS\u00a043, 439\u2013561 (2006)","journal-title":"Bull. AMS"},{"key":"42_CR19","unstructured":"Jagannathan, S., Pandrurangan, G., Srinivasan, S.: Query protocols for highly resilient peer-to-peer networks. In: ISCA PDCS 2006, pp. 247\u2013252 (2006)"},{"key":"42_CR20","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley, Chichester (2000)"},{"key":"42_CR21","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Sudakov, B.: Pseudo-random graphs. In: Proceedings of the Conference on Finite and Infinite Sets. Bolyai Society Mathematical Studies, vol.\u00a015, pp. 199\u2013262 (2006)","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Law, C., Siu, K.-Y.: Distributed construction of random expander networks. In: IEEE INFOCOM 2003, pp. 2133\u20132143 (2003)","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"42_CR23","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1017\/S0963548301005089","volume":"11","author":"C. McDiarmid","year":"2002","unstructured":"McDiarmid, C.: Concentration for independent permutations. Combinatorics, Probability and Computing\u00a011, 163\u2013178 (2002)","journal-title":"Combinatorics, Probability and Computing"},{"key":"42_CR24","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0012-365X(91)90112-F","volume":"91","author":"A. Nilli","year":"1991","unstructured":"Nilli, A.: On the second eigenvalue of a graph. Discrete Math.\u00a091, 207\u2013210 (1991)","journal-title":"Discrete Math."},{"key":"42_CR25","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1109\/JSAC.2003.814666","volume":"21","author":"G. Pandurangan","year":"2003","unstructured":"Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter peer-to-peer networks. IEEE Journal on Selected Areas in Communications\u00a021, 995\u20131002 (2003)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"42_CR26","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF02699376","volume":"81","author":"M. Talagrand","year":"1995","unstructured":"Talagrand, M.: Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes \u00c9tudes Sci. Publ. Math.\u00a081, 73\u2013205 (1995)","journal-title":"Inst. Hautes \u00c9tudes Sci. Publ. Math."},{"key":"42_CR27","doi-asserted-by":"crossref","unstructured":"Thomason, A.: Pseudo-random graphs. In: Proceedings of Random Graphs, pp. 307\u2013331 (1987)","DOI":"10.1016\/S0304-0208(08)73063-9"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:31Z","timestamp":1606187131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}