{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T05:50:06Z","timestamp":1733896206610,"version":"3.30.1"},"reference-count":21,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3827,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1016\/s0166-218x(02)00560-7","type":"journal-article","created":{"date-parts":[[2002,10,28]],"date-time":"2002-10-28T16:05:14Z","timestamp":1035821114000},"page":"33-54","source":"Crossref","is-referenced-by-count":7,"title":["Improving the efficiency of parallel minimum spanning tree algorithms"],"prefix":"10.1016","volume":"126","author":[{"given":"Ka Wong","family":"Chong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yijie","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshihide","family":"Igarashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tak Wah","family":"Lam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00560-7_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","article-title":"Sorting in clogn parallel steps","volume":"3","author":"Ajtai","year":"1983","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, R. Raman, Sorting in linear time? Proceedings of the 1995 Symposium on Theory of Computing, 1995, pp. 427\u2013436.","key":"10.1016\/S0166-218X(02)00560-7_BIB2","DOI":"10.1145\/225058.225173"},{"key":"10.1016\/S0166-218X(02)00560-7_BIB3","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","article-title":"New connectivity and MSF algorithms for shuffle-exchange network and PRAM","volume":"C-36","author":"Awerbuch","year":"1987","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0166-218X(02)00560-7_BIB4","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1145\/358628.358650","article-title":"Efficient parallel algorithms for some graph problems","volume":"25","author":"Chin","year":"1982","journal-title":"Comm. ACM"},{"unstructured":"K.W. Chong, Finding minimum spanning trees on the EREW PRAM, Proceedings of the 1996 International Computer Symposium (ICS\u201996), Taiwan, 1996, pp. 7\u201314.","key":"10.1016\/S0166-218X(02)00560-7_BIB5"},{"unstructured":"K.W. Chong, Y. Han, T.W. Lam, On the parallel time complexity of undirected connectivity and minimum spanning trees. Proceedings of the 1999 10th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201999), Baltimore, MD, January 1999, pp. 225\u2013234.","key":"10.1016\/S0166-218X(02)00560-7_BIB6"},{"key":"10.1016\/S0166-218X(02)00560-7_BIB7","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","article-title":"Parallel merge sort","volume":"17","author":"Cole","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00560-7_BIB8","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(88)90186-X","article-title":"An optimally efficient selection algorithm","volume":"26","author":"Cole","year":"1987","journal-title":"Inform. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"R. Cole, P. N. Klein, R.E. Tarjan, Finding minimum spanning forests in logarithmic time and linear work using random sampling, SPAA\u201996, pp. 243\u2013250.","key":"10.1016\/S0166-218X(02)00560-7_BIB9","DOI":"10.1145\/237502.237563"},{"issue":"1","key":"10.1016\/S0166-218X(02)00560-7_BIB10","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","article-title":"Upper and lower time bounds for parallel random access machines without simultaneous write","volume":"15","author":"Cook","year":"1986","journal-title":"SIAM J. Comput."},{"year":"1988","author":"Gibbons","series-title":"Efficient Parallel Algorithms","key":"10.1016\/S0166-218X(02)00560-7_BIB11"},{"doi-asserted-by":"crossref","unstructured":"T. Goldberg, U. Zwick, Optimal deterministic approximate parallel prefix sums and their applications. Proceedings of the Third Israel Symposium on Theory and Computing Systems, 1995, pp. 220\u2013228.","key":"10.1016\/S0166-218X(02)00560-7_BIB12","DOI":"10.1109\/ISTCS.1995.377028"},{"doi-asserted-by":"crossref","unstructured":"Y. Han, X. Shen, Conservative algorithms for parallel and sequential integer sorting, Proceedings of the 1995 International Computing and Combinatorics Conference, XiAn, China, Lecture Notes in Computer Science, Vol. 959, Springer, Berlin, August 1995, pp. 324\u2013333.","key":"10.1016\/S0166-218X(02)00560-7_BIB13","DOI":"10.1007\/BFb0030847"},{"unstructured":"Y. Han, X. Shen. Parallel integer sort is more efficient than parallel comparison sorting on exclusive write PRAMs, Proceedings of the 1999 10th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201999), Baltimore, MD, January 1999, pp. 419\u2013428.","key":"10.1016\/S0166-218X(02)00560-7_BIB14"},{"key":"10.1016\/S0166-218X(02)00560-7_BIB15","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/359138.359141","article-title":"Computing connected components on parallel computers","volume":"22","author":"Hirshberg","year":"1979","journal-title":"Comm. ACM"},{"key":"10.1016\/S0166-218X(02)00560-7_BIB16","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1006\/jagm.1995.1043","article-title":"A parallel algorithm for computing minimum spanning trees","volume":"19","author":"Johnson","year":"1995","journal-title":"J. Algorithms"},{"unstructured":"D.R. Karger, Random sampling in graph optimization problems, Ph.D. Thesis. Department of Computer Science, Stanford University, 1995.","key":"10.1016\/S0166-218X(02)00560-7_BIB17"},{"doi-asserted-by":"crossref","unstructured":"C.K. Poon, V. Ramachandran, A randomized linear work EREW PRAM algorithm to find a minimum spanning forest, Proceedings of the Eighth Annual International Symposium on Algorithms and Computation, 1997, pp. 212\u2013222.","key":"10.1016\/S0166-218X(02)00560-7_BIB18","DOI":"10.1007\/3-540-63890-3_24"},{"issue":"3","key":"10.1016\/S0166-218X(02)00560-7_BIB19","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1137\/0214051","article-title":"On parallel searching","volume":"14","author":"Snir","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00560-7_BIB20","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","article-title":"An efficient parallel biconnectivity algorithm","volume":"14","author":"Tarjan","year":"1985","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0166-218X(02)00560-7_BIB21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1142\/S012962649700005X","article-title":"Simple and work-efficient parallel algorithms for the minimum spanning tree problem","volume":"7","author":"Zaroliagis","year":"1997","journal-title":"Parallel Process. Lett."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02005607?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02005607?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T22:09:19Z","timestamp":1733868559000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02005607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["S0166218X02005607"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00560-7","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}