{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T23:25:08Z","timestamp":1791156308326,"version":"4.1.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1988,11,1]],"date-time":"1988-11-01T00:00:00Z","timestamp":594345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1988,11]]},"DOI":"10.1007\/bf01762110","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T06:22:38Z","timestamp":1118902958000},"page":"53-77","source":"Crossref","is-referenced-by-count":41,"title":["Communication-efficient parallel algorithms for distributed random-access machines"],"prefix":"10.1007","volume":"3","author":[{"given":"Charles E.","family":"Leiserson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce M.","family":"Maggs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01762110_CR1","first-page":"95","volume-title":"Advances in Computing Research, Vol. 2","author":"S. N. Bhatt","year":"1984","unstructured":"S. N. Bhatt and C. E. Leiserson, How to assemble tree machines, inAdvances in Computing Research, Vol. 2 (F. P. Preparata, ed.), JAI Press, Greenwich, CT, 1984, pp. 95\u2013114."},{"issue":"2","key":"BF01762110_CR2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent, The parallel evaluation of general arithmetic expressions,J. Assoc. Comput. Mach.,21 (2), 1974, 201\u2013208.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"BF01762110_CR3","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TC.1982.1675982","volume":"31","author":"R. P. Brent","year":"1982","unstructured":"R. P. Brent and H. T. Kung, A regular layout for parallel adders,IEEE Trans. Comput.,31 (3), 1982, 260\u2013264.","journal-title":"IEEE Trans. Comput."},{"key":"BF01762110_CR4","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations,Ann. of Math. Stat.,23, 1952, 493\u2013507.","journal-title":"Ann. of Math. Stat."},{"key":"BF01762110_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms,Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, May 1986, pp. 206\u2013219.","DOI":"10.1145\/12130.12151"},{"issue":"6","key":"BF01762110_CR6","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1038\/scientificamerican0685-18","volume":"252","author":"A. K. Dewdney","year":"1985","unstructured":"A. K. Dewdney, Computer recreations,Sci. Amer. 252 (6), 1985, 18\u201329.","journal-title":"Sci. Amer."},{"issue":"4","key":"BF01762110_CR7","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"M. J. Fischer","year":"1980","unstructured":"M. J. Fischer and R. E. Ladner, Parallel prefix computation,J. Assoc. Comput. Mach.,27 (4), 1980, 831\u2013838.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01762110_CR8","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and R. E. Tarjan, A new approach to the maximum flow problem,Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, May 1986, pp. 136\u2013146.","DOI":"10.1145\/12130.12144"},{"key":"BF01762110_CR9","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and R. E. Tarjan, Solving minimum-cost flow problems by successive approximation,Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, May 1987, pp. 7\u201318.","DOI":"10.1145\/28395.28397"},{"key":"BF01762110_CR10","doi-asserted-by":"crossref","unstructured":"R. I. Greenberg and C. E. Leiserson, Randomized routing on fat-trees,Proceedings of the 26th Annual Symposium on Foundations of Computer Science, October 1985, pp. 241\u2013249.","DOI":"10.1109\/SFCS.1985.46"},{"issue":"12","key":"BF01762110_CR11","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1145\/7902.7903","volume":"29","author":"W. D. Hillis","year":"1986","unstructured":"W. D. Hillis and G. L. Steele, Jr., Data parallel algorithms,Comm. ACM,29 (12), 1986, 1170\u20131183.","journal-title":"Comm. ACM"},{"key":"BF01762110_CR12","doi-asserted-by":"crossref","unstructured":"A. R. Karlin and E. Upfal, Parallel hashing-an efficient implementation of shared memory,Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, May 1986, pp. 160\u2013168.","DOI":"10.1145\/12130.12146"},{"key":"BF01762110_CR13","unstructured":"J. Kilian, Private communication, July 1986."},{"key":"BF01762110_CR14","volume-title":"The Art of Computer Programming, Vol. 1","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Vol. 1, Second Edition, Addison-Wesley, Reading, MA, 1973.","edition":"Second Edition"},{"key":"BF01762110_CR15","first-page":"256","volume-title":"S1AM Sparse Matrix Proceedings","author":"H. T. Kung","year":"1978","unstructured":"H. T. Kung and C. E. Leiserson, Systolic arrays (for VLSI), inS1AM Sparse Matrix Proceedings (I. S. Duff and G. W. Stewart, ed.), SIAM, Philadelphia, PA, 1978, pp. 256\u2013282."},{"issue":"3","key":"BF01762110_CR16","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1137\/0215057","volume":"15","author":"F. T. Leighton","year":"1986","unstructured":"F. T. Leighton and A. L. Rosenberg, Three-dimensional circuit layouts,SIAM J. Comput.,15 (3), 1986, 793\u2013813.","journal-title":"SIAM J. Comput."},{"issue":"10","key":"BF01762110_CR17","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/TC.1985.6312192","volume":"34","author":"C. E. Leiserson","year":"1985","unstructured":"C. E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing,IEEE Trans. Comput.,34 (10), 1985, 892\u2013901.","journal-title":"IEEE Trans. Comput."},{"key":"BF01762110_CR18","volume-title":"Area-Efficient VLSI Computation","author":"C. E. Leiserson","year":"1983","unstructured":"C. E. Leiserson,Area-Efficient VLSI Computation, MIT Press, Cambridge, MA, 1983."},{"key":"BF01762110_CR19","volume-title":"Communication-efficient parallel graph algorithms","author":"C. E. Leiserson","year":"1986","unstructured":"C. E. Leiserson and B. M. Maggs, Communication-efficient parallel graph algorithms, Technical Memo MIT\/ LCS\/TM-318, MIT Laboratory for Computer Science, Cambridge, MA, December 1986."},{"issue":"2","key":"BF01762110_CR20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan, A planar separator theorem,SIAM J. Appl. Math.,36 (2), 1979, 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01762110_CR21","volume-title":"Communication-Efficient Parallel Graph Algorithms, Master's thesis","author":"B. M. Maggs","year":"1986","unstructured":"B. M. Maggs, Communication-Efficient Parallel Graph Algorithms, Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 1986."},{"key":"BF01762110_CR22","doi-asserted-by":"crossref","unstructured":"G. Miller and J. Reif, Parallel tree contraction and its application,Proceedings of the 26th Annual Symposium on Foundations of Computer Science, October 1985, pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"issue":"7","key":"BF01762110_CR23","first-page":"589","volume":"7","author":"Yu. Ofman","year":"1963","unstructured":"Yu. Ofman, On the algorithmic complexity of discrete functions,Soviet Phys. Dokl. 7 (7), 1963, 589\u2013591.","journal-title":"Soviet Phys. Dokl."},{"issue":"10","key":"BF01762110_CR24","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1109\/TC.1985.6312198","volume":"34","author":"G. F. Pfister","year":"1985","unstructured":"G. F. Pfister and V. A. Norton, \u201cHot spot\u201d contention and combining in multistage interconnection networks,IEEE Trans. Comput.,34 (10), 1985, 943\u2013948.","journal-title":"IEEE Trans. Comput."},{"key":"BF01762110_CR25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, AnO(logn) parallel connectivity algorithm,J. Algorithms,3, 1982, 57\u201367.","journal-title":"J. Algorithms"},{"key":"BF01762110_CR26","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983."},{"key":"BF01762110_CR27","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan and U. Vishkin, Finding biconnected components and computing tree functions in logarithmic parallel time,Proceedings of the 25th Annual Symposium on Foundations of Computer Science, October 1984, pp. 12\u201320.","DOI":"10.1109\/SFCS.1984.715896"},{"key":"BF01762110_CR28","volume-title":"Ph.D. thesis","author":"C. D. Thompson","year":"1980","unstructured":"C. D. Thompson, A Complexity Theory for VLSI, Ph.D. thesis, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1980."},{"issue":"2","key":"BF01762110_CR29","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1137\/0211027","volume":"11","author":"L. G. Valiant","year":"1982","unstructured":"L. G. Valiant, A scheme for fast parallel communication,SIAM J. Comput.,11(2), 1982, 350\u2013361.","journal-title":"SIAM J. Comput."},{"key":"BF01762110_CR30","volume-title":"Ph.D. thesis","author":"J. C. Wyllie","year":"1979","unstructured":"J. C. Wyllie, The Complexity of Parallel Computations, Ph.D. thesis, Cornell University, Ithaca, NY, 1979."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762110.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01762110\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01762110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T15:26:50Z","timestamp":1586273210000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01762110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,11]]},"references-count":30,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1988,11]]}},"alternative-id":["BF01762110"],"URL":"https:\/\/doi.org\/10.1007\/bf01762110","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,11]]}}}