{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:51Z","timestamp":1773704811370,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T00:00:00Z","timestamp":1500940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,7,25]]},"DOI":"10.1145\/3087801.3087827","type":"proceedings-article","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T17:51:38Z","timestamp":1500573098000},"page":"131-140","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Distributed MST and Routing in Almost Mixing Time"],"prefix":"10.1145","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,7,25]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"David Aldous and Jim Fill. 2002. Reversible Markov chains and random walks on graphs. (2002).  David Aldous and Jim Fill. 2002. Reversible Markov chains and random walks on graphs. (2002)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000125"},{"key":"e_1_3_2_1_3_1","unstructured":"Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons.  Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.29"},{"key":"e_1_3_2_1_5_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Avin Chen"},{"key":"e_1_3_2_1_6_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Avin Chen"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28421"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 318--327","author":"Awerbuch Baruch","year":"2004"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_20"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767447"},{"key":"e_1_3_2_1_11_1","volume-title":"Automata, Languages, and Programming","author":"Berns Andrew"},{"key":"e_1_3_2_1_12_1","volume-title":"Proc. of the Symp. on Theory of Comp. (STOC). 531--539","author":"Broder AZ","year":"1997"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792232021"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.7"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729542"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993686"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582745"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835745"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_22_1","volume-title":"Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA). 359--368","author":"Elkin Michael","year":"2004"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007407"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968802"},{"key":"e_1_3_2_1_25_1","volume-title":"Rand. and Approx. Techniques in Comp. Sci","author":"Frieze Alan M"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366103"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/323596.323612"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Robert G. Gallager Pierre A. Humblet and Philip M. Spira. 1983. A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and systems (TOPLAS) 5 1 (1983) 66--77.  Robert G. Gallager Pierre A. Humblet and Philip M. Spira. 1983. A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Programming Languages and systems (TOPLAS) 5 1 (1983) 66--77.","DOI":"10.1145\/357195.357200"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261118"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09620-9_13"},{"key":"e_1_3_2_1_38_1","volume-title":"Distributed Computing","author":"Hegeman James W"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897638"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0047-8"},{"key":"e_1_3_2_1_42_1","unstructured":"Janne H Korhonen. 2016. Deterministic MST Sparsification in the Congested Clique. arXiv preprint arXiv:1605.02022 (2016).  Janne H Korhonen. 2016. Deterministic MST Sparsification in the Congested Clique. arXiv preprint arXiv:1605.02022 (2016)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0099-z"},{"key":"e_1_3_2_1_44_1","volume-title":"Fast Distributed Construction of K-dominating Sets and Applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). 238--251","author":"Kutten Shay","year":"1995"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"e_1_3_2_1_46_1","volume-title":"Proc. of a Workshop on Randomized Parallel Comp.","author":"Leighton FT","year":"1996"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700379760"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.1998.649241"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.383984"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0127-6"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777428"},{"key":"e_1_3_2_1_54_1","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics Paul erdos is eighty 2 1 (1993) 1--46.  L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics Paul erdos is eighty 2 1 (1993) 1--46."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073992"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_30"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00224-7"},{"key":"e_1_3_2_1_59_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: bringing order to the web. (1999).  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: bringing order to the web. (1999)."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.78"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993865"},{"key":"e_1_3_2_1_62_1","first-page":"995","article-title":"Building low-diameter peer-to-peer networks. Selected Areas in Communications","volume":"21","author":"Peer Networks Pandurangan Gopal","year":"2003","journal-title":"IEEE Journal on"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993851"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125897"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_3_2_1_67_1","unstructured":"Daniel A. Spielman. 2015. Spectral Graph Theory : Random Walks on Graphs. lecture notes. (2015). http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/2012\/lect10--12.pdf.  Daniel A. Spielman. 2015. Spectral Graph Theory : Random Walks on Graphs. lecture notes. (2015). http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/2012\/lect10--12.pdf."},{"key":"e_1_3_2_1_68_1","unstructured":"Frank Spitzer. 2013. Principles of random walk. Vol. 34. Springer Science & Business Media.  Frank Spitzer. 2013. Principles of random walk. Vol. 34. Springer Science & Business Media."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/964723.383071"},{"key":"e_1_3_2_1_70_1","unstructured":"G Weiss. 2005. Aspects and Applications of the Random Walk (Random Materials & Processes S.). (2005).  G Weiss. 2005. Aspects and Applications of the Random Walk (Random Materials & Processes S.). (2005)."}],"event":{"name":"PODC '17: ACM Symposium on Principles of Distributed Computing","location":"Washington DC USA","acronym":"PODC '17","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087827","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3087801.3087827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:07Z","timestamp":1750217407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,25]]},"references-count":70,"alternative-id":["10.1145\/3087801.3087827","10.1145\/3087801"],"URL":"https:\/\/doi.org\/10.1145\/3087801.3087827","relation":{},"subject":[],"published":{"date-parts":[[2017,7,25]]},"assertion":[{"value":"2017-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}