{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:45:40Z","timestamp":1725486340962},"reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108276"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0105139","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T05:24:42Z","timestamp":1181625882000},"page":"480-492","source":"Crossref","is-referenced-by-count":1,"title":["Binary trees and parallel scheduling algorithms"],"prefix":"10.1007","author":[{"given":"Eliezer","family":"Dekel","sequence":"first","affiliation":[]},{"given":"Sartaj","family":"Sahni","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"34_CR1","unstructured":"Agerwala, T. and Lint, B., \"Communication in Parallel Algorithms for Boolean Matrix Multiplication,\" Proc. 1978 Int. Conf. on Parallel Processing, IEEE pp. 146\u2013153, 1978."},{"key":"34_CR2","unstructured":"Arjomandi, E., \"A study of parallelism in graph theory,\" Ph.D. thesis, Computer Science department, University of Toronto, December 1975."},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1002\/nav.3800210112","volume":"21","author":"K. R. Baker","year":"1974","unstructured":"Baker, K. R. and Su, Z.-S., \"Sequencing with due-dates and early start times to minimize maximum tardiness,\" Naval Res. Logist. Quart. vol. 21, pp. 171\u2013176, 1974.","journal-title":"Naval Res. Logist. Quart."},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Batcher, K. E., \"Sorting networks and their applications,\" Proc. AFIPS 1968 SJCC, Vol. 32., AFIPS Press, Montvale, NJ, pp. 307\u2013314.","DOI":"10.1145\/1468075.1468121"},{"key":"34_CR5","unstructured":"Batcher, K. E., \"MPP-a massively parallel processor,\" Proc. 1979 Int. Conf. on Parallel Procesing, IEEE, p 249, 1979"},{"issue":"5","key":"34_CR6","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/0020-0190(77)90015-1","volume":"6","author":"J. Blazewicz","year":"1977","unstructured":"Blazewicz, J., \"Simple algorithm for multiprocessor scheduling to meet deadlines,\" Info. Processing Letters, Vol. 6, Number 5, pp. 162\u2013164, 1977.","journal-title":"Info. Processing Letters"},{"issue":"2","key":"34_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"Brent, R. P., \"The parallel evaluation of general arithmetic expressions,\" JACM, Vol. 21, No. 2, April, 1974, pp. 201\u2013206.","journal-title":"JACM"},{"key":"34_CR8","doi-asserted-by":"crossref","unstructured":"Csanky, L., \"Fast parallel matrix inversion algorithms,\" Proc. 6th IEEE Symp. on Found. of Computer Science, October 1975, pp. 11\u201312.","DOI":"10.1109\/SFCS.1975.14"},{"key":"34_CR9","unstructured":"Dekel, E., Nassimi, D., and Sahni S., \"Parallel matrix and graph algorithms,\" University of Minnesota, TR 79-10, 1979. To appear in SIAM. J. Compute."},{"key":"34_CR10","unstructured":"Dekel, E. and Sahni, S., \"Parallel scheduling algorithms,\" University of Minnesota, Technical Report, TR 81-1, 1981."},{"key":"34_CR11","unstructured":"Eckstein, D., \"Parallel graph processing using depth-first search and breadth first search,\" Ph.D. Thesis, University of Iowa, 1977."},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Hirschberg, D. S., \"Parallel algorithms for the transitive closure and the connected component problems,\" Proc. 8th ACM Symp. on Theo. of Comput., May 1976, pp. 55\u201357.","DOI":"10.1145\/800113.803631"},{"issue":"8","key":"34_CR13","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1145\/359576.359582","volume":"21","author":"D. S. Hirschberg","year":"1978","unstructured":"Hirschberg, D. S., \"Fast parallel sorting algorithms,\" CACM, Vol. 21, No. 8, August 1978, pp. 657\u2013661.","journal-title":"CACM"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"W. A. Horn","year":"1974","unstructured":"Horn, W. A., \"Some simple scheduling algorithms,\" Naval Res. Logist. Quart., Vol. 21, pp. 177\u2013185, 1974.","journal-title":"Naval Res. Logist. Quart."},{"key":"34_CR15","volume-title":"Fundamentals of computer algorithms","author":"E. Horowitz","year":"1978","unstructured":"Horowitz, E. and Sahni, S., \"Fundamentals of computer algorithms,\" Computer Science Press, Potomac, MD, 1978."},{"key":"34_CR16","series-title":"Research report","volume-title":"Scheduling a production line to minimize tardiness","author":"J. K. Jackson","year":"1955","unstructured":"Jackson, J. K., \"Scheduling a production line to minimize tardiness,\" Research report 43, Management Science Research Project, University of California, Los Angeles, 1955."},{"key":"34_CR17","volume-title":"Complexity of computer computations","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M., \"Reducibility among combinatorial problems,\" In: Miller, R. E., and Thatcher, J. W. (eds.), Complexity of computer computations,\" Plenum Press, New York, 1972."},{"key":"34_CR18","volume-title":"The Art of Computer Programming Vol. 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"Knuth, D. E., \"The Art of Computer Programming Vol. 3: Sorting and Searching,\" Addison-Wesley, Reading, Mass., 1973."},{"issue":"5","key":"34_CR19","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1109\/TC.1976.1674637","volume":"C-25","author":"T. Lang","year":"1976","unstructured":"Lang, T., \"Interconnections between processors and memory modules using the shuffle-exchange network.\" IEEE Trans. on Computers, C-25, No. 5, May, 1976, pp. 496\u2013503.","journal-title":"IEEE Trans. on Computers"},{"issue":"1","key":"34_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1109\/TC.1976.5009205","volume":"C-25","author":"T. Lang","year":"1976","unstructured":"Lang, T. and Stone, H., \"A shuffle exchange network with simplified control,\" IEEE Trans. on Computers, C-25, No. 1, January, 1976, pp. 55\u201365.","journal-title":"IEEE Trans. on Computers"},{"key":"34_CR21","unstructured":"Lawler, E. L., \"Sequencing to minimize the weighted number of tardy jobs,\" Rev. Francaise Automat. Informat. Recherche Operationalle, 10.5, Suppl. 27\u201333, 1976."},{"key":"34_CR22","series-title":"Mathematical Centre Tract","volume-title":"Sequencing by enumerative methods","author":"J. K. Lenstra","year":"1977","unstructured":"Lenstra, J. K., \"Sequencing by enumerative methods,\" Mathematical Centre Tract 69, Mathematisch Centrum, Amsterdam, 1977."},{"key":"34_CR23","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"J. M. Moore","year":"1968","unstructured":"Moore, J. M., \"An n job, one machine sequencing algorithm for minimizing the number of late jobs,\" Management Sci. 15, pp. 102\u2013109, 1968.","journal-title":"Management Sci."},{"issue":"2","key":"34_CR24","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/321879.321882","volume":"22","author":"D. E. Muller","year":"1975","unstructured":"Muller, D. E., and Preparata, F. P., \"Bounds to complexities of networks for sorting and for switching,\" JACM, Vol. 22, No. 2, April 1975, pp. 195\u2013201.","journal-title":"JACM"},{"key":"34_CR25","first-page":"189","volume":"7","author":"I. Munro","year":"1973","unstructured":"Munro, I. and Paterson, M., \"Optimal algorithms for parallel polynomial evaluation,\" JCSS, Vol. 7, 1973, pp. 189\u2013198.","journal-title":"JCSS"},{"issue":"1","key":"34_CR26","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TC.1979.1675216","volume":"C-28","author":"D. Nassimi","year":"1979","unstructured":"Nassimi, D. and Sahni, S., \"Bitonic sort on a mesh-connected parallel computer,\" IEEE Trans. on Computers, C-28, No. 1, January 1979, pp. 2\u20137","journal-title":"IEEE Trans. on Computers"},{"issue":"1","key":"34_CR27","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/322169.322172","volume":"27","author":"D. Nassimi","year":"1980","unstructured":"Nassimi, D. and Sahni, S., \"An optimal routing algorithm for mesh connected parallel computer,\" JACM 27, 1, pp. 6\u201329, 1980.","journal-title":"JACM"},{"key":"34_CR28","doi-asserted-by":"crossref","unstructured":"Nassimi, D. and Sahni, S., \"Parallel permutation and sorting algorithms and a new generalized connection network,\" JACM, to appear.","DOI":"10.1145\/322326.322329"},{"key":"34_CR29","doi-asserted-by":"crossref","unstructured":"Nassimi, D. and Sahni, S., \"Data broadcasting in SIMD Computers,\" Proc. 1980 Int. Conf. on Parallel Processing, IEEE, to appear in IEEE Trans on computers.","DOI":"10.1109\/TC.1981.6312172"},{"issue":"7","key":"34_CR30","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1109\/TC.1978.1675167","volume":"C-27","author":"F. P. Preparata","year":"1978","unstructured":"Preparata, F. P., \"New parallel-sorting schemes,\" IEEE Trans. on Computers, C-27, No. 7, July 1978, pp. 669\u2013673.","journal-title":"IEEE Trans. on Computers"},{"key":"34_CR31","volume-title":"Machine scheduling problems: classification, complexity, and computations","author":"Rinnooy","year":"1976","unstructured":"Rinnooy, Kan, A. H. G., \"Machine scheduling problems: classification, complexity, and computations,\" Nighoff, The Hague, 1976."},{"key":"34_CR32","volume-title":"Parallel algorithms for graph theoretic problems","author":"C. Savage","year":"1978","unstructured":"Savage, C., \"Parallel algorithms for graph theoretic problems,\" Ph.D. Thesis, University of Illinois, Urbana, August 1978."},{"key":"34_CR33","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1109\/TC.1979.1675280","volume":"C-28","author":"H. Siegal","year":"1979","unstructured":"Siegal, H., \"A model of SIMD machines and a comparison of various interconnection networks,\" Proc. IEEE Trans on Computers, C-28, 1979, pp. 907\u2013917.","journal-title":"Proc. IEEE Trans on Computers"},{"key":"34_CR34","series-title":"Lecture Notes in Economics and Mathematical Systems","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/978-3-642-80784-8_26","volume-title":"Symp. on the Theory of Scheduling and its applications","author":"J. B. Sidney","year":"1973","unstructured":"Sidney, J. B., \"An extension of Moore's due date algorithm,\" In S. E. Elmagharaby (ed) 1973, Symp. on the Theory of Scheduling and its applications, Lecture Notes in Economics and Mathematical Systems, 86 Springer, Berlin, pp. 393\u2013398, 1973."},{"key":"34_CR35","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. E. Smith","year":"1956","unstructured":"Smith, W. E., \"Various optimizers for single-stage production,\" Naval Res. Logist. Quart., Vol. 3, pp. 59\u201366, 1956.","journal-title":"Naval Res. Logist. Quart."},{"key":"34_CR36","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1109\/T-C.1971.223205","volume":"C-20","author":"H. Stone","year":"1971","unstructured":"Stone, H., \"Parallel processing with the perfect shuffle,\" IEEE Trans. on Computers, C-20, 1971, pp. 153\u2013161.","journal-title":"IEEE Trans. on Computers"},{"issue":"12","key":"34_CR37","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1109\/TC.1978.1675014","volume":"C-27","author":"C. D. Thompson","year":"1978","unstructured":"Thompson, C. D., \"Generalized connection networks for parallel processor interconnection,\" IEEE Trans. on Computers, C-27, No. 12, December, 1978, pp. 1119\u20131125.","journal-title":"IEEE Trans. on Computers"},{"key":"34_CR38","unstructured":"Thompson, C. D., and Kung, H. T., \"Sorting an a mesh connected parallel computer,\""},{"key":"34_CR39","unstructured":"Dekel, E. and Sahni, S., \"Binary Trees and Parallel Schedualing Algorithms\" University of Minnesota, technical Report 80-19."}],"container-title":["Lecture Notes in Computer Science","Conpar 81"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0105139.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:18:57Z","timestamp":1607552337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0105139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540108276"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/bfb0105139","relation":{},"subject":[]}}