{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:40:00Z","timestamp":1742391600795},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540663294"},{"type":"electronic","value":"9783540484134"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/978-3-540-48413-4_24","type":"book-chapter","created":{"date-parts":[[2011,1,14]],"date-time":"2011-01-14T12:52:41Z","timestamp":1295009561000},"page":"233-244","source":"Crossref","is-referenced-by-count":4,"title":["A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"36","author":"B. Awerbuch","year":"1987","unstructured":"Awerbuch, B., Shiloach, Y.: New connectivity and MSF algorithms for shuffle-exchange networks and PRAM. IEEE Trans. Computers\u00a0C-36, 1258\u20131263 (1987)","journal-title":"IEEE Trans. Computers C-"},{"key":"24_CR2","unstructured":"Bor\u016fvka, O.: O jist\u00e9m probl\u00e9mu minima\u00e9ln\u00edm. Moravsk\u00e9 P\u0159\u00edrodov\u00e9deck\u00e9 Spole\u010dnosti 3, 37\u201358 (1926) ( in Czech)"},{"key":"24_CR3","unstructured":"Chong, K.W., Han, Y., Lam, T.W.: On the parallel time complexity of undirected connectivity and minimum spanning trees. In: Proc. SODA 1999, pp. 225\u2013234 (1999)"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Cole, R., Klein, P.N., Tarjan, R.E.: A linear-work parallel algorithm for finding minimum spanning trees. In: Proc. SPAA, pp. 11\u201315 (1994)","DOI":"10.1145\/195058.195084"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Klein, P.N., Tarjan, R.E.: Finding minimum spanning trees in logarithmic time and linear work using random sampling. In: Proc. SPAA, pp. 213\u2013219 (1996)","DOI":"10.1145\/237502.237563"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Gazit, H.: An optimal randomized parallel algorithm for finding connected components in a graph. In: SICOMP, vol.\u00a020, pp. 1046\u20131067 (1991)","DOI":"10.1137\/0220066"},{"key":"24_CR7","unstructured":"Gibbons, P.B., Matias, Y., Ramachandran, V.: The QRQW PRAM: Accounting for contention in parallel algorithms. In: Proc. SODA, pp. 638\u2013648 (1994) (SICOMP 1999, to appear)"},{"key":"#cr-split#-24_CR8.1","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B., Matias, Y., Ramachandran, V.: Can a shared-memory model serve as a bridging model for parallel computation? In: Proc. SPAA, pp. 72???83 (1997);","DOI":"10.1145\/258492.258500"},{"key":"#cr-split#-24_CR8.2","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B., Matias, Y., Ramachandran, V.: Can a shared-memory model serve as a bridging model for parallel computation? In: Proc. SPAA, pp. 72\u201383 (1997); Theory of Comp. Sys. (1999) (to appear)","DOI":"10.1145\/258492.258500"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Halperin, S., Zwick, U.: An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM. In: Proc. SPAA, pp. 1\u201310 (1994)","DOI":"10.1145\/181014.181017"},{"key":"24_CR10","unstructured":"Halperin, S., Zwick, U.: Optimal randomized EREW PRAM algorithms for rinding spanning forests and for other basic graph connectivity problems. In: Proc. SODA 1996, pp. 438\u2013447 (1996)"},{"key":"24_CR11","first-page":"227","volume":"54","author":"D.B. Johnson","year":"1997","unstructured":"Johnson, D.B., Metaxas, P.: Connected components in O(log3\/2 n) parallel time for CREW PRAM. JCSS\u00a054, 227\u2013242 (1997)","journal-title":"JCSS"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02526037","volume":"18","author":"V. King","year":"1997","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica\u00a018, 263\u2013270 (1997)","journal-title":"Algorithmica"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. JACM\u00a042, 321\u2013328 (1995)","journal-title":"JACM"},{"issue":"3","key":"24_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(97)00050-1","volume":"62","author":"V. King","year":"1997","unstructured":"King, V., Poon, C.K., Ramachandran, V., Sinha, S.: An optimal EREW PRAM algorithm for minimum spanning tree verification. IPL\u00a062(3), 153\u2013159 (1997)","journal-title":"IPL"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-63890-3_24","volume-title":"Algorithms and Computation","author":"C.K. Poon","year":"1997","unstructured":"Poon, C.K., Ramachandran, V.: A randomized linear work EREW PRAM algorithm to find a minimum spanning forest. In: Leong, H.-V., Jain, S., Imai, H. (eds.) ISAAC 1997. LNCS, vol.\u00a01350, pp. 212\u2013222. Springer, Heidelberg (1997)"},{"key":"24_CR16","unstructured":"Poon, C.K., Ramachandran, V.: Private communication (1998)"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Pettie, S., Ramachandran, V.: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest Tech. Report TR99-13, Univ. of Texas at Austin (1999)","DOI":"10.1007\/978-3-540-48413-4_24"},{"issue":"8","key":"24_CR18","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. CACM\u00a033(8), 103\u2013111 (1990)","journal-title":"CACM"}],"container-title":["Lecture Notes in Computer Science","Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-48413-4_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T21:19:18Z","timestamp":1559942358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-48413-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540663294","9783540484134"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-48413-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]}}}