{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:33:29Z","timestamp":1767339209038,"version":"3.32.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"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":[[1990,6]]},"DOI":"10.1007\/bf01840376","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T22:41:35Z","timestamp":1119998495000},"page":"43-64","source":"Crossref","is-referenced-by-count":71,"title":["Efficient parallel algorithms for graph problems"],"prefix":"10.1007","volume":"5","author":[{"given":"Clyde P.","family":"Kruskal","sequence":"first","affiliation":[]},{"given":"Larry","family":"Rudolph","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Snir","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01840376_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974."},{"key":"BF01840376_CR2","doi-asserted-by":"crossref","unstructured":"M. J. Atallah and S. E. Hambrusch, Solving Tree Problems on a Mesh-Connected Processor Array,Proc. 26th Annual Symposium on Foundations of Computer Science, Oct. 1985, 222\u2013231.","DOI":"10.1109\/SFCS.1985.53"},{"key":"BF01840376_CR3","doi-asserted-by":"crossref","unstructured":"D. Cheriton and R. E. Tarjan, Finding Minimum Spanning Trees,SIAM J. Comput., 1976, 724\u2013742.","DOI":"10.1137\/0205051"},{"key":"BF01840376_CR4","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms,Proc. 18th Annual ACM Symposium on Theory of Computation, 1986, 206\u2013219.","DOI":"10.1145\/12130.12151"},{"key":"BF01840376_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 Annual Symposium on Foundations of Computer Science, 1986, 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"BF01840376_CR6","unstructured":"R. Cole and U. Vishkin, The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithm Time, Submitted for Publication."},{"key":"BF01840376_CR7","unstructured":"D. M. Eckstein, Parallel Processing Using Depth-First and Breadth-First Search, Ph.D. Thesis, University of Iowa, July 1977."},{"key":"BF01840376_CR8","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, Addison-Wesley, Reading, Mass., 1973."},{"key":"BF01840376_CR9","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"34","author":"C. P. Kruskal","year":"1985","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir, The Power of Parallel Prefix,IEEE Trans. Comput.,34, 1985, 965\u2013968.","journal-title":"IEEE Trans. Comput."},{"key":"BF01840376_CR10","unstructured":"S. C. Kwan and W. L. Ruzzo, Adaptive Parallel Algorithms for Finding Minimum Spanning Trees,Proc. 1984 International Conference on Parallel Processing, Aug. 1984, 439\u2013443."},{"key":"BF01840376_CR11","doi-asserted-by":"crossref","unstructured":"R. Ladner and M. Fischer, Parallel Prefix Computation,J. Assoc. Comput. Mach., 1980, 831\u2013838.","DOI":"10.1145\/322217.322232"},{"key":"BF01840376_CR12","doi-asserted-by":"crossref","unstructured":"G. Miller and J. Reif, Parallel Tree Contraction and Its Application,Proc. 26th Annual Symposium on Foundations of Computer Science, 1985, 496\u2013503.","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF01840376_CR13","doi-asserted-by":"crossref","unstructured":"J. T. Schwartz, Ultracomputers,ACM Trans. Program. Lang. Systems, 1980, 484\u2013521.","DOI":"10.1145\/357114.357116"},{"key":"BF01840376_CR14","doi-asserted-by":"crossref","unstructured":"M. Snir, On Parallel Searching,Proc. ACM Symposium on Distributed Computing, Aug. 1982, 242\u2013253.","DOI":"10.1145\/800220.806703"},{"key":"BF01840376_CR15","unstructured":"Q. F. Stout, Tree-Based Graph Algorithms for Some Parallel Computers,Proc. 1985 International Conference on Parallel Processing, Aug. 1985, 727\u2013731."},{"key":"BF01840376_CR16","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan and U. Vishkin, Finding Biconnected Components and Computing Tree Functions in Logarithmic Time,Proc. 25th Annual Symposium on Foundations of Computer Science, Oct. 1984, 12\u201320.","DOI":"10.1109\/SFCS.1984.715896"},{"key":"BF01840376_CR17","doi-asserted-by":"crossref","unstructured":"U. Vishkin, Randomized Speedups in Parallel Computations,Proc. 16th Annual ACM Symposium on Theory of Computing, April 1984, 230\u2013239.","DOI":"10.1145\/800057.808686"},{"key":"BF01840376_CR18","volume-title":"Ph.D. Dissertation","author":"J. C. Wyllie","year":"1979","unstructured":"J. C. Wyllie, The Complexity of Parallel Computations, Ph.D. Dissertation, Department of Computer Science, Cornell University, Ithaca, N.Y., 1979."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840376.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840376\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T03:13:53Z","timestamp":1735787633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":18,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["BF01840376"],"URL":"https:\/\/doi.org\/10.1007\/bf01840376","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}