{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:51:01Z","timestamp":1756572661523},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,10,25]],"date-time":"2008-10-25T00:00:00Z","timestamp":1224892800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,1]]},"DOI":"10.1007\/s00453-008-9245-4","type":"journal-article","created":{"date-parts":[[2008,10,24]],"date-time":"2008-10-24T14:56:59Z","timestamp":1224860219000},"page":"51-88","source":"Crossref","is-referenced-by-count":22,"title":["On Mixing and Edge Expansion Properties in\u00a0Randomized Broadcasting"],"prefix":"10.1007","volume":"56","author":[{"given":"Thomas","family":"Sauerwald","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,25]]},"reference":[{"key":"9245_CR1","first-page":"157","volume":"7","author":"S.L. Bezrukov","year":"1999","unstructured":"Bezrukov, S.L.: Edge isoperimetric problems on graphs. Graph Theory Comb. Biol. 7, 157\u2013197 (1999)","journal-title":"Graph Theory Comb. Biol."},{"issue":"6","key":"9245_CR2","doi-asserted-by":"crossref","first-page":"2508","DOI":"10.1109\/TIT.2006.874516","volume":"52","author":"S. Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Trans. Inf. Theory IEEE\/ACM Trans. Netw. 52(6), 2508\u20132530 (2006)","journal-title":"IEEE Trans. Inf. Theory IEEE\/ACM Trans. Netw."},{"key":"9245_CR3","doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry,\u00a0D.: Epidemic algorithms for replicated database maintenance. In: 6th ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201312 (1987)","DOI":"10.1145\/41840.41841"},{"key":"9245_CR4","doi-asserted-by":"crossref","unstructured":"Diaconis, P.: Group Representations in Probability and Statistics. Lecture Notes-Monograph Series, vol. 11 (1988)","DOI":"10.1214\/lnms\/1215467407"},{"issue":"1","key":"9245_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/rsa.3240010105","volume":"1","author":"P. Diaconis","year":"1990","unstructured":"Diaconis, P., Graham, R.L., Morrison, J.A.: Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Struct. Algorithms 1(1), 51\u201372 (1990)","journal-title":"Random Struct. Algorithms"},{"issue":"7","key":"9245_CR6","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0167-8191(99)00018-6","volume":"25","author":"R. Diekmann","year":"1999","unstructured":"Diekmann, R., Frommer, A., Monien, B.: Efficient schemes for nearest neighbor load balancing. Parallel Comput. 25(7), 789\u2013812 (1999)","journal-title":"Parallel Comput."},{"key":"9245_CR7","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R.: On the communication complexity of randomized broadcasting in random-like graphs. In: 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 148\u2013157 (2006)","DOI":"10.1145\/1148109.1148135"},{"key":"9245_CR8","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. In: 17th International Symposium on Algorithms and Computation (ISAAC), pp. 349\u2013358 (2006)","DOI":"10.1007\/11940128_36"},{"key":"9245_CR9","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R., Sauerwald, T.: Broadcasting vs. mixing and information dissemination on Cayley graphs. In: 24th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 163\u2013174 (2007)","DOI":"10.1007\/978-3-540-70918-3_15"},{"key":"9245_CR10","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On the power of memory in randomized broadcasting. In: 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 218\u2013227 (2008)"},{"issue":"4","key":"9245_CR11","doi-asserted-by":"crossref","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 Struct. Algorithms 1(4), 447\u2013460 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"9245_CR12","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1016\/0167-8191(96)00023-3","volume":"22","author":"L. Ga\u0327sieniec","year":"1996","unstructured":"Ga\u0327sieniec, L., Pelc, A.: Adaptive broadcasting with faulty nodes. Parallel Comput. 22, 903\u2013912 (1996)","journal-title":"Parallel Comput."},{"key":"9245_CR13","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probability and Random Processes","author":"G.R. Grimmett","year":"2001","unstructured":"Grimmett, G.R., Stirzaker, D.R.: Probability and Random Processes, 3rd edn. Oxford University Press, London (2001)","edition":"3"},{"key":"9245_CR14","volume-title":"Dissemination of Information in Communication Networks","author":"J. Hromkovic\u0306","year":"2005","unstructured":"Hromkovic\u0306, J., Klasing, R., Pelc, A., Ruz\u0306ic\u0306ka, P., Unger, W.: Dissemination of Information in Communication Networks. Springer, Berlin (2005)"},{"key":"9245_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., V\u00f6cking, B.: Randomized rumor spreading. In: 41st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 565\u2013574 (2000)","DOI":"10.1109\/SFCS.2000.892324"},{"key":"9245_CR16","doi-asserted-by":"crossref","unstructured":"Leighton, T., Maggs, B., Sitamaran, R.: On the fault tolerance of some popular bounded-degree networks. In: 33rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 542\u2013552 (1992)","DOI":"10.1109\/SFCS.1992.267797"},{"key":"9245_CR17","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1080\/00029890.1964.11992272","volume":"7","author":"J.H. Lindsey","year":"1964","unstructured":"Lindsey, J.H.: Optimal assignment of numbers to vertices. Am. Math. Mon. 7, 508\u2013516 (1964)","journal-title":"Am. Math. Mon."},{"key":"9245_CR18","volume-title":"Lectures on the Coupling Method","author":"T. Lindvall","year":"1992","unstructured":"Lindvall, T.: Lectures on the Coupling Method. Wiley, New York (1992)"},{"key":"9245_CR19","first-page":"1","volume":"2","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Random walks on graphs: a survey. Comb. Paul Erd\u00f6s Eighty 2, 1\u201346 (1993)","journal-title":"Comb. Paul Erd\u00f6s Eighty"},{"key":"9245_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"key":"9245_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"9245_CR22","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1137\/0147013","volume":"47","author":"B. Pittel","year":"1987","unstructured":"Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213\u2013223 (1987)","journal-title":"SIAM J. Appl. Math."},{"key":"9245_CR23","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1098\/rspa.1927.0118","volume":"115","author":"A.G. McKendrick","year":"1927","unstructured":"McKendrick, A.G., Kermack, W.O.: Contributions to the mathematical theory of epidemics. Proc. R. Soc. Lond. Ser. A 115, 700\u2013721 (1927)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"9245_CR24","volume-title":"Introduction to Probability Models","author":"S. Ross","year":"2003","unstructured":"Ross, S.: Introduction to Probability Models, 8th edn. Academic Press, San Diego (2003)","edition":"8"},{"key":"9245_CR25","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1017\/S0963548300000390","volume":"1","author":"A. Sinclair","year":"1996","unstructured":"Sinclair, A.: Improved bounds for mixing rates of Markov chains and multicommodity flow. Comb. Probab. Comput. 1, 351\u2013370 (1996)","journal-title":"Comb. Probab. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9245-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9245-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9245-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T00:35:41Z","timestamp":1709339741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9245-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,25]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["9245"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9245-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,25]]}}}