On coalescence time in graphs : When is coalescing as fast as meeting?
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 127986518
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611975482.59
- Title of conference / published proceedings
- Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms : 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019; San Diego; United States; 6 January 2019 through 9 January 2019
- First page
- 956
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- December
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Applications of this work go beyond random walks, e.g., the results directly give bounds on the consensus time in the voter model. They can also be used to bound the all-to-all broadcasting time in a network of randomly moving robots. The paper was the first to relate the coalescing time to the meeting and mixing time. The paper also gives first improvements since Broder and Karlin 1989 on the hitting time and cover time of random walk, reigniting the study of this topic (e.g. Oliveira and Peres ANALCO19). The 78-page full version of this work is available at https://arxiv.org/abs/1611.02460.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -