{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:13Z","timestamp":1759639033118,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-9988160"],"award-info":[{"award-number":["CCR-9988160"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004926","name":"Texas Higher Education Coordinating Board","doi-asserted-by":"publisher","award":["003658-0029-1999"],"award-info":[{"award-number":["003658-0029-1999"]}],"id":[{"id":"10.13039\/100004926","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis problem, the parallel connected components and parallel minimum spanning tree problems, and the local sorting and set maxima problems. (For the first two problems there are provably optimal deterministic algorithms with unknown, and possibly superlinear, running times.) One downside of the randomized methods for solving these problems is that they use a number of random bits linear in the size of input. In this article we develop some general methods for reducing exponentially the consumption of random bits in comparison-based algorithms. In some cases we are able to reduce the number of random bits from linear to nearly constant, without affecting the expected running time.<\/jats:p>\n          <jats:p>\n            Most of our results are obtained by adjusting or reorganizing existing randomized algorithms to work well with a pairwise or\n            <jats:italic>O<\/jats:italic>\n            (1)-wise independent sampler. The prominent exception, and the main focus of this article, is a linear-time randomized minimum spanning tree algorithm that is\n            <jats:italic>not<\/jats:italic>\n            derived from the well-known Karger-Klein-Tarjan algorithm. In many ways it resembles more closely the deterministic minimum spanning tree algorithms based on soft heaps. Further, using our algorithm as a guide, we present a unified view of the existing \u201cnongreedy\u201d minimum spanning tree algorithms. Concepts from the Karger-Klein-Tarjan algorithm, such as\n            <jats:italic>F<\/jats:italic>\n            -lightness, MST verification, and sampled graphs, are related to the concepts of edge corruption, subgraph contractibility, and soft heaps, which are the basis of the deterministic MST algorithms of Chazelle and Pettie-Ramachandran.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328916","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Randomized minimum spanning tree algorithms using exponentially fewer random bits"],"prefix":"10.1145","volume":"4","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28410"},{"key":"e_1_2_1_2_1","unstructured":"Bach E. and Shallit J. 1996. Algorithmic Number Theory. The MIT Press Cambridge MA.   Bach E. and Shallit J. 1996. Algorithmic Number Theory. The MIT Press Cambridge MA."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_5_1","unstructured":"Bor\u016fvka O. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 3 37--58. In Czech.  Bor\u016fvka O. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 3 37--58. In Czech."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276764"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355554"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375847"},{"volume-title":"Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), 14--25","author":"Cohen A.","key":"e_1_2_1_10_1","unstructured":"Cohen , A. , and Wigderson , A . 1989. Dispersers, deterministic amplification, and weak random sources . In Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), 14--25 . Cohen, A., and Wigderson, A. 1989. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), 14--25."},{"key":"e_1_2_1_11_1","unstructured":"Cole R. 1999. Personal communication.  Cole R. 1999. Personal communication."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237563"},{"volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 478--491","author":"Cole R.","key":"e_1_2_1_13_1","unstructured":"Cole , R. , and Vishkin , U . 1986. Approximate and exact parallel scheduling with applications to list, tree, and graph problems . In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 478--491 . Cole, R., and Vishkin, U. 1986. Approximate and exact parallel scheduling with applications to list, tree, and graph problems. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 478--491."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90019-X"},{"key":"e_1_2_1_15_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62047"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221070"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199353895"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288611"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65954"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579168"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220066"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222020"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1985.10011"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322206"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0078"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1146"},{"volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 248--253","author":"Impagliazzo R.","key":"e_1_2_1_30_1","unstructured":"Impagliazzo , R. , and Zuckerman , D . 1989. How to recycle random bits . In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 248--253 . Impagliazzo, R., and Zuckerman, D. 1989. How to recycle random bits. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 248--253."},{"key":"e_1_2_1_31_1","unstructured":"Jarn\u00edk V. 1930. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ca Moravsk\u00e9 P&rbreve;\u00edrodov\u0115deck\u00e9 Spole&cbreve;nosti 6 57--63. In Czech.  Jarn\u00edk V. 1930. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ca Moravsk\u00e9 P&rbreve;\u00edrodov\u0115deck\u00e9 Spole&cbreve;nosti 6 57--63. In Czech."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996762"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366879"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Karp R. M. and Ramachandran V. 1990. Parallel algorithms for shared-memory machines. In Handbook of Computer Science. MIT Press\/Elsevier 869--942.   Karp R. M. and Ramachandran V. 1990. Parallel algorithms for shared-memory machines. In Handbook of Computer Science. MIT Press\/Elsevier 869--942.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73042"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02526037"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00050-1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579443"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the Annual ACM\/SIAM Symposium on Discrete Algorithm (SODA), 400--409","author":"Liberatore V.","year":"1998","unstructured":"Liberatore , V. 1998 . Matroid decomposition methods for the set maxima problem . In Proceedings of the Annual ACM\/SIAM Symposium on Discrete Algorithm (SODA), 400--409 . Liberatore, V. 1998. Matroid decomposition methods for the set maxima problem. In Proceedings of the Annual ACM\/SIAM Symposium on Discrete Algorithm (SODA), 400--409."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80043-8"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press New York.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80029-3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_96"},{"volume-title":"Proceedings of the 13th Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA), 713--722","author":"Pettie S.","key":"e_1_2_1_48_1","unstructured":"Pettie , S. , and Ramachandran , V . 2002a. Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms . In Proceedings of the 13th Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA), 713--722 . Pettie, S., and Ramachandran, V. 2002a. Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms. In Proceedings of the 13th Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA), 713--722."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505243"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700371065"},{"key":"e_1_2_1_51_1","article-title":"Shortest connection networks and some generalizations. Bell","author":"Prim R. C.","year":"1957","unstructured":"Prim , R. C. 1957 . Shortest connection networks and some generalizations. Bell Syst. Tech. J., 1389--1401. Prim, R. C. 1957. Shortest connection networks and some generalizations. Bell Syst. Tech. J., 1389--1401.","journal-title":"Syst. Tech. J., 1389--1401."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90137-5"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328916","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328916","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:00Z","timestamp":1750258320000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328916"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328916","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}