{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T12:10:12Z","timestamp":1737288612667,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662006"},{"type":"electronic","value":"9783540486862"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_45","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:12Z","timestamp":1184601252000},"page":"452-461","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improving Parallel Computation with Fast Integer Sorting"],"prefix":"10.1007","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":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtia","year":"1983","unstructured":"M. Ajtia, J. Koml\u00f3s, E. Szemer\u00e9di. Sorting in c log n parallel steps. Combinatorica, 3, pp. 1\u201319(1983).","journal-title":"Combinatorica"},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, R. Raman. Sorting in linear time? Proc. 1995 Symposium on Theory of Computing, 427\u2013436(1995).","DOI":"10.1145\/225058.225173"},{"key":"45_CR3","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"C-36","author":"B. Awerbuch","year":"1987","unstructured":"B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. on Computers, C-36, 1258\u20131263, 1987.","journal-title":"IEEE Trans. on Computers"},{"key":"45_CR4","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1145\/358628.358650","volume":"25","author":"F. Y. Chin","year":"1982","unstructured":"F. Y. Chin, J. Lam and I-N. Chen. Efficient parallel algorithms for some graph problems. Comm. ACM, 25 (1982), pp. 659\u2013665.","journal-title":"Comm. ACM"},{"key":"45_CR5","unstructured":"K. W. Chong. Finding minimum spanning trees on the EREW PRAM. Proc. 1996 International Computer Symposium (ICS'96), Taiwan, 1996, pp. 7\u201314."},{"key":"45_CR6","unstructured":"K. W. Chong, Y. Han, T. W. Lam. On the parallel time complexity of undirected connectivity and minimum spanning trees. Proc. 1999 Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, 225\u2013234(1999)."},{"key":"45_CR7","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM J. Comput., 17 (1988), pp. 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"45_CR8","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0020-0190(88)90186-X","volume":"26","author":"R. Cole","year":"1987","unstructured":"R. Cole. An optimally efficient selection algorithm. Information Processing Letters, 26, 295\u2013299(1987\/88).","journal-title":"Information Processing Letters"},{"key":"45_CR9","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'96, pp. 243\u2013250.","DOI":"10.1145\/237502.237563"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"T. Goldberg and U. Zwick. Optimal deterministic approxiamate parallel prefix sums and their applications. Proc. 3rd Israel Symposium on Theory and Computing Systems, 220\u2013228(1995).","DOI":"10.1109\/ISTCS.1995.377028"},{"key":"45_CR11","unstructured":"Y. Han, X. Shen. Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs. Proc. 1999 Tenth ACM-SIAM Symposium on Discrete Algorithms (SODA'99), Baltimore, Maryland, 419\u2013428(1999)."},{"key":"45_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/BFb0030847","volume-title":"Proc. 1995 International Computing and Combinatorics Conference (COCOON'95)","author":"Y. Han","year":"1995","unstructured":"Y. Han, X. Shen. Conservative algorithms for parallel and sequential integer sorting. Proc. 1995 International Computing and Combinatorics Conference (COCOON'95), Lecture Notes in Computer Science 959, 324\u2013333 (August, 1995)."},{"key":"45_CR13","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/359138.359141","volume":"22","author":"D. S. Hirshberg","year":"1979","unstructured":"D. S. Hirshberg, A. K. Chandra and D. V. Sarwate. Computing connected components on parallel computers. Comm. ACM, 22 (1979), pp. 461\u2013464.","journal-title":"Comm. ACM"},{"key":"45_CR14","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1006\/jagm.1995.1043","volume":"19","author":"D. B. Johnson","year":"1995","unstructured":"D. B. Johnson and P. Metaxas. A parallel algorithm for computing minimum spanning trees. J. of Algorithms, 19, 383\u2013401(1995).","journal-title":"J. of Algorithms"},{"key":"45_CR15","doi-asserted-by":"crossref","unstructured":"C. K. Poon, V. Ramachandran. A randomized linear work EREW PRAM algorithm to find a minimum spanning forest. Proc. 8th Annual International Symposium on Algorithms and Computation, 1997, pp. 212\u2013222.","DOI":"10.1007\/3-540-63890-3_24"},{"key":"45_CR16","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM J. Comput., 14, pp. 862\u2013874(1985).","journal-title":"SIAM J. Comput."},{"issue":"1","key":"45_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1142\/S012962649700005X","volume":"7","author":"C.D. Zaroliagis","year":"1997","unstructured":"C.D. Zaroliagis. Simple and work-e.cient parallel algorithms for the minimum spanning tree problem. Parallel Processing Letters, Vol. 7,No. 1, 25\u201337(1997).","journal-title":"Parallel Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:42:44Z","timestamp":1737286964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_45","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"25 June 1999","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}