{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T15:05:01Z","timestamp":1726412701764},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616276"},{"type":"electronic","value":"9783540706366"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"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":[[1996]]},"DOI":"10.1007\/bfb0024747","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:17:56Z","timestamp":1132384676000},"page":"543-554","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient parallel algorithms for scheduling with tree precedence constraints"],"prefix":"10.1007","author":[{"given":"Ernst W.","family":"Mayr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"Stadtherr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"70_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka. A simple parallel tree contraction algorithm. J. Algorithms, 10:287\u2013302, 1989.","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"R. J. Anderson and G. L. Miller. Deterministic parallel list ranking. In J. H. Reif, editor, Proc. of the 3rd AWOC, LNCS 319, pages 81\u201390. Springer-Verlag, 1988.","key":"70_CR2","DOI":"10.1007\/BFb0040376"},{"issue":"2","key":"70_CR3","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0218014","volume":"18","author":"G. Bilardi","year":"1989","unstructured":"G. Bilardi and A. Nicolau. Adaptive bitonic sorting: An optimal parallel algorithm for shared-memory machines. SIAM J. Comput., 18(2):216\u2013228, 1989.","journal-title":"SIAM J. Comput."},{"key":"70_CR4","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1287\/moor.2.3.275","volume":"2","author":"P. Brucker","year":"1977","unstructured":"P. Brucker, M. Garey, and D. S. Johnson. Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Math. Oper. Res., 2:275\u2013284, 1977.","journal-title":"Math. Oper. Res."},{"key":"70_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(92)90078-A","volume":"41","author":"C. C. Chen","year":"1992","unstructured":"C. C.-Y. Chen and S. K. Das. Breadth-first traversal of trees and integer sorting in parallel. Inf. Process. Lett., 41:39\u201349, 1992.","journal-title":"Inf. Process. Lett."},{"key":"70_CR6","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:770\u2013785, 1988.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"70_CR7","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. Approximate parallel scheduling, Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Comput., 17(1):128\u2013142, 1988.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin. Optimal parallel algorithms for expression tree evaluation and list ranking. In J. H. Reif, editor, Proc. of the 3rd AWOC, LNCS 319, pages 91\u2013100. Springer-Verlag, 1988.","key":"70_CR8","DOI":"10.1007\/BFb0040377"},{"key":"70_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","volume":"1","author":"E. Dekel","year":"1984","unstructured":"E. Dekel and S. Sahni. A parallel matching algorithm for convex bipartite graphs and applications to scheduling. J. Parallel Distrib. Comput., 1:185\u2013205, 1984.","journal-title":"J. Parallel Distrib. Comput."},{"key":"70_CR10","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/0743-7315(86)90014-6","volume":"3","author":"D. Dolev","year":"1986","unstructured":"D. Dolev, E. Upfal, and M. K. Warmuth. The parallel complexity of scheduling with precedence constraints. J. Parallel Distrib. Comput., 3:553\u2013576, 1986.","journal-title":"J. Parallel Distrib. Comput."},{"issue":"1","key":"70_CR11","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/0890-5401(89)90027-8","volume":"81","author":"A. Gibbons","year":"1989","unstructured":"A. Gibbons and W. Rytter. Optimal parallel algorithms for dynamic expression evaluation and context-free recognition. Inf. Comput., 81(1):32\u201345, 1989.","journal-title":"Inf. Comput."},{"key":"70_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(89)90138-5","volume":"33","author":"T. Hagerup","year":"1989","unstructured":"T. Hagerup and C. R\u00fcb. Optimal merging and sorting on the EREW PRAM. Inf. Process. Lett., 33:181\u2013185, 1989.","journal-title":"Inf. Process. Lett."},{"key":"70_CR13","first-page":"39","volume-title":"Advances in Computing Research; Parallel and Distributed Computing, volume 4","author":"D. Helmbold","year":"1987","unstructured":"D. Helmbold and E. W. Mayr. Fast scheduling algorithms on parallel computers. In F. P. Preparata, editor, Advances in Computing Research; Parallel and Distributed Computing, volume 4, pages 39\u201368. JAI Press Inc., Greenwich, CT-London, 1987."},{"issue":"6","key":"70_CR14","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1287\/opre.9.6.841","volume":"9","author":"T. C. Hu","year":"1961","unstructured":"T. C. Hu. Parallel sequencing and assembly line problems. Operations Research, 9(6):841\u2013848, 1961.","journal-title":"Operations Research"},{"doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju and A. L. Delcher. Optimal parallel evaluation of tree-structured computations by raking (extended abstract). In J. H. Reif, editor, Proc. of the 3rd AWOC, LNCS 319, pages 101\u2013110. Springer-Verlag, 1988.","key":"70_CR15","DOI":"10.1007\/BFb0040378"},{"issue":"4","key":"70_CR16","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer. Parallel prefix computation. J. ACM, 27(4):831\u2013838, 1980.","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its application. In Proc. of the 26th FOCS, pages 478\u2013489. IEEE, 1985.","key":"70_CR17","DOI":"10.1109\/SFCS.1985.43"},{"issue":"4","key":"70_CR18","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(4):862\u2013874, 1985.","journal-title":"SIAM J. Comput"},{"issue":"3","key":"70_CR19","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J. D. Ullman","year":"1975","unstructured":"J. D. Ullman. NP-complete scheduling problems. J. Comput. Syst. Sci., 10(3):-384\u2013393, 1975.","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Euro-Par'96 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T00:35:10Z","timestamp":1587342910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616276","9783540706366"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0024747","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"10 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}