{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:08Z","timestamp":1750220888420,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,9,30]],"date-time":"2019-09-30T00:00:00Z","timestamp":1569801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["679660"],"award-info":[{"award-number":["679660"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M005038\/1"],"award-info":[{"award-number":["EP\/M005038\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            We present new bounds on the cover time of the\n            <jats:italic>coalescing-branching random walk<\/jats:italic>\n            process COBRA. The COBRA process, introduced in Dutta et al. [9], can be viewed as spreading a single item of information throughout an undirected graph in synchronised rounds. In each round, each vertex that has received the information in the previous round (possibly simultaneously from more than one neighbour and possibly not for the first time), \u201cpushes\u201d the information to\n            <jats:italic>k<\/jats:italic>\n            randomly selected neighbours. The COBRA process is typically studied for integer branching rates\n            <jats:italic>k<\/jats:italic>\n            \u2265 2 (with the case\n            <jats:italic>k<\/jats:italic>\n            =1 corresponding to a random walk). The aim of the process is to propagate the information quickly, but with a limited number of transmissions per vertex per round.\n          <\/jats:p>\n          <jats:p>\n            The COBRA cover time is the expected number of rounds until all vertices have received the information at least once. Our main results are bounds of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            + (\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            )\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) on the COBRA cover time for arbitrary connected graphs with\n            <jats:italic>n<\/jats:italic>\n            vertices,\n            <jats:italic>m<\/jats:italic>\n            edges and maximum graph degree\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            , and bounds of\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            +\n            <jats:italic>r<\/jats:italic>\n            \/(1\u2212\u03bb)) log\n            <jats:italic>n<\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            ((1\/(1\u2212 \u03bb)\n            <jats:sup>2<\/jats:sup>\n            )log\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>r<\/jats:italic>\n            -regular connected graphs with the second largest eigenvalue \u03bb in absolute value. Our bounds for general graphs are always\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ), decreasing to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) for constant degree graphs, while the best previous bound is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.75<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ). Our first bound for regular graphs applied to the lazy variant of the COBRA process is\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            +\n            <jats:italic>r<\/jats:italic>\n            \/\u03c6\n            <jats:sup>2<\/jats:sup>\n            )log\n            <jats:italic>n<\/jats:italic>\n            ), where \u03c6 is the conductance of the graph. The best previous results for the COBRA process imply for this case only a bound of\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            \/\u03c6\n            <jats:sup>2<\/jats:sup>\n            )log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            To derive our bounds, we develop the following new approach to analysing the performance of the COBRA process. We introduce a type of infection process, which we call the\n            <jats:italic>Biased Infection with Persistent Source<\/jats:italic>\n            (BIPS) process, show that BIPS can be viewed as dual to COBRA, and obtain bounds for COBRA by analysing the convergence of BIPS.\n          <\/jats:p>","DOI":"10.1145\/3364206","type":"journal-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T14:04:16Z","timestamp":1572876256000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["New Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs"],"prefix":"10.1145","volume":"6","author":[{"given":"Colin","family":"Cooper","sequence":"first","affiliation":[{"name":"King\u2019s College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomasz","family":"Radzik","sequence":"additional","affiliation":[{"name":"King\u2019s College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Rivera","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000125"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.112"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790190144"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3173043"},{"key":"e_1_2_1_5_1","article-title":"\/10. Multiple random walks in random regular graphs","volume":"23","author":"Cooper Colin","year":"2009","unstructured":"Colin Cooper , Alan Frieze , and Tomasz Radzik . 2009 \/10. Multiple random walks in random regular graphs . SIAM J. Discrete Math. 23 , 4 (2009\/10), 1738--1761. DOI:https:\/\/doi.org\/10.1137\/080729542 10.1137\/080729542 Colin Cooper, Alan Frieze, and Tomasz Radzik. 2009\/10. Multiple random walks in random regular graphs. SIAM J. Discrete Math. 23, 4 (2009\/10), 1738--1761. DOI:https:\/\/doi.org\/10.1137\/080729542","journal-title":"SIAM J. Discrete Math."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933119"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087564"},{"key":"e_1_2_1_8_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"Devdatt","year":"2009","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press , Cambridge. DOI:https:\/\/doi.org\/10.1017\/CBO9780511581274 10.1017\/CBO9780511581274 Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge. DOI:https:\/\/doi.org\/10.1017\/CBO9780511581274"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486197"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2817830"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. LIPIcs. Leibniz Int. Proc. Inform.","volume":"9","author":"Giakkoupis George","year":"2011","unstructured":"George Giakkoupis . 2011 . Tight bounds for rumor spreading in graphs of a given conductance . In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. LIPIcs. Leibniz Int. Proc. Inform. , Vol. 9 . Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 57--68. George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. LIPIcs. Leibniz Int. Proc. Inform., Vol. 9. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 57--68."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935791"},{"key":"e_1_2_1_15_1","first-page":"93","article-title":"Approximate counting, uniform generation and rapidly mixing Markov chains. Info","volume":"82","author":"Sinclair Alistair","year":"1989","unstructured":"Alistair Sinclair and Mark Jerrum . 1989 . Approximate counting, uniform generation and rapidly mixing Markov chains. Info . Comput. 82 , 1 (1989), 93 -- 133 . DOI:https:\/\/doi.org\/10.1016\/0890-5401(89)90067-9 10.1016\/0890-5401(89)90067-9 Alistair Sinclair and Mark Jerrum. 1989. Approximate counting, uniform generation and rapidly mixing Markov chains. Info. Comput. 82, 1 (1989), 93--133. DOI:https:\/\/doi.org\/10.1016\/0890-5401(89)90067-9","journal-title":"Comput."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:26Z","timestamp":1750203866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,30]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3364206"],"URL":"https:\/\/doi.org\/10.1145\/3364206","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2019,9,30]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}