{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:00Z","timestamp":1725663360205},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540529217"},{"type":"electronic","value":"9783540471776"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52921-7_58","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:47:48Z","timestamp":1330206468000},"page":"86-100","source":"Crossref","is-referenced-by-count":0,"title":["Parallel algorithms for linked list and beyond"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"10_CR1","unstructured":"R. J. Anderson, G. L. Miller. Optimal parallel algorithms for the list ranking problem, USC-Tech. Rept. 1986."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"R. J. Anderson, G. L. Miller. Deterministic parallel list ranking. LNCS 319 (J. H. Reif ed.), 81\u201390.","DOI":"10.1007\/BFb0040376"},{"key":"10_CR3","unstructured":"R. A. Borodin and J. E. Hopcroft. Routing, merging and sorting on parallel models of computation. Proc. 14th ACM Symposium on Theory of Computing, 206\u2013219 (1986)."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"B. S. Chlebus, K. Diks, T. Hagerup, T. Radzik. New simulations between CRCW PRAMs. LNCS 380, 95\u2013104.","DOI":"10.1007\/3-540-51498-8_9"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to list, tree and graph problems, Proc. 27th Symp. on Foundations of Comput. Sci., IEEE, 478\u2013491 (1986).","DOI":"10.1109\/SFCS.1986.10"},{"issue":"4","key":"10_CR6","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1137\/0401045","volume":"1","author":"A. V. Goldberg","year":"1988","unstructured":"A. V. Goldberg, S. A. Plotkin, G. E. Shannon. Parallel symmetry-breaking in sparse graphs, SIAM J. on Discrete Math., Vol. 1, No. 4, 447\u2013471 (Nov., 1988).","journal-title":"SIAM J. on Discrete Math."},{"key":"10_CR7","volume-title":"Designing fast and efficient parallel algorithms","author":"Y. Han","year":"1987","unstructured":"Y. Han. Designing fast and efficient parallel algorithms. Ph.D. Thesis, Duke University, Durham, NC 27706, 1987."},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/0743-7315(89)90005-1","volume":"6","author":"Y. Han","year":"1989","unstructured":"Y. Han. Parallel algorithms for computing linked list prefix. J. of Parallel and Distributed Computing 6, 537\u2013557 (1989).","journal-title":"J. of Parallel and Distributed Computing"},{"key":"10_CR9","first-page":"246","volume-title":"Proc. ACM Symp. on Parallel Algorithms and Architectures","author":"Y. Han","year":"1989","unstructured":"Y. Han. Matching partition a linked list and its optimization. Proc. ACM Symp. on Parallel Algorithms and Architectures, Sante Fe, New Mexico, 246\u2013253 (1989)."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Y. Han. An optimal linked list prefix algorithm on a local memory computer. Proc. 1989 ACM Computer Science Conf., Lousville, Kentucky, 278\u2013286 (1989).","DOI":"10.1145\/75427.75462"},{"key":"10_CR11","unstructured":"Y. Han. On the chromatic number of Shuffle graphs. TR. No. 140-89, Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA."},{"issue":"5","key":"10_CR12","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0020-0190(88)90084-1","volume":"27","author":"H. Jung","year":"1988","unstructured":"H. Jung, K. Mehlhorn. Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees, Information Processing Letters, Vol. 27, No. 5, 227\u2013236 (1988).","journal-title":"Information Processing Letters"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"N. C. Kalra, P. C. P. Bhatt. Parallel algorithms for tree traversals, Parallel Computing, Vol. 2, No. 2, June 1985.","DOI":"10.1016\/0167-8191(85)90026-2"},{"key":"10_CR14","unstructured":"C. P. Kruskal, T. Madej, L. Rudolph. Parallel prefix on fully connected direct connection machine. Proc. 1986 Int. Conf. on Parallel Processing, 278\u2013284."},{"key":"10_CR15","unstructured":"C. P. Kruskal, L. Rudolph and M. Snir. Efficient parallel algorithms for graph problems. Proc. 1986 International Conf. on Parallel Processing, 869\u2013876."},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"N. Linial. Distributive graph algorithms \u2014 global solutions from local data. Proc. 1987 IEEE Symposium on Foundations of Computer Science, 331\u2013336 (1987).","DOI":"10.1109\/SFCS.1987.20"},{"key":"10_CR17","unstructured":"G. L. Miller, J. H. Reif. Parallel tree contraction and its application. Proc. 1985 IEEE Foundations of Computer Science, 478\u2013489."},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"I. Parberry. On the time required to sum n semigroup elements on a parallel machine with simultaneous writes. LNCS, 227, 296\u2013304.","DOI":"10.1007\/3-540-16766-8_27"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"J. H. Reif. An optimal parallel algorithm for integer sorting, Proc. 26th Symp. on Foundations of Computer Sci., IEEE, 291\u2013298 (1985).","DOI":"10.1109\/SFCS.1985.9"},{"key":"10_CR20","unstructured":"K. W. Ryu, J. J\u00e1J\u00e1. List ranking on the hypercube. Proc. 1989 Int. Conf. on Parallel Processing. St. Charles, Illinois, (Aug. 1989)."},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1137\/0214051","volume":"14","author":"M. Snir","year":"1985","unstructured":"M. Snir. On parallel searching. SIAM J. Comput, Vol. 14, No. 3, 688\u2013708 (Aug., 1985).","journal-title":"SIAM J. Comput"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BF01171114","volume":"27","author":"E. Sperner","year":"1928","unstructured":"E. Sperner. Ein satz \u00fcber untermenger endlichen menge, Math. Z. 27 (1928), 544\u2013548.","journal-title":"Math. Z."},{"key":"10_CR23","unstructured":"R. E. Tarjan, U. Vishkin. Finding biconnected components and computing tree functions in logarithmic time, 25th Symp. on Foundations of Computer Sci., IEEE, 12\u201320."},{"key":"10_CR24","unstructured":"J. D. Ullman. Computational aspects of VLSI, Computer Science Press, 1984."},{"key":"10_CR25","unstructured":"R. A. Wagner, Y. Han. Parallel algorithms for bucket sorting the data dependent prefix problem. Proc. 1986 Int. Conf. on Parallel Processing, 924\u2013930."},{"key":"10_CR26","volume-title":"The complexity of parallel computation. TR 79-387","author":"J. C. Wyllie","year":"1979","unstructured":"J. C. Wyllie. The complexity of parallel computation. TR 79-387, Department of Computer Science, Cornell University, Ithaca, NY, 1979."}],"container-title":["Lecture Notes in Computer Science","Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52921-7_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:44Z","timestamp":1605648344000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52921-7_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540529217","9783540471776"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-52921-7_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}