{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T06:54:56Z","timestamp":1761893696707,"version":"3.41.0"},"reference-count":141,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1984,9,2]],"date-time":"1984-09-02T00:00:00Z","timestamp":462931200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[1984,9,2]]},"DOI":"10.1145\/2514.2515","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:32:04Z","timestamp":1027769524000},"page":"319-348","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":115,"title":["Parallel graph algorithms"],"prefix":"10.1145","volume":"16","author":[{"given":"Michael J.","family":"Quinn","sequence":"first","affiliation":[{"name":"Washington State Univ., Pullman, WA"}]},{"given":"Narsingh","family":"Deo","sequence":"additional","affiliation":[{"name":"Washington State Univ., Pullman, WA"}]}],"member":"320","published-online":{"date-parts":[[1984,9,2]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"AHO A. HOPCROFT J AND ULLMAN J. 1974. The Design and Analysis of Computer Algorithms Addison-Wesley Reading Mass.   AHO A. HOPCROFT J AND ULLMAN J. 1974. The Design and Analysis of Computer Algorithms Addison-Wesley Reading Mass."},{"volume-title":"Proceed~ngs of the West Coast Conference on Combinator~cs, Graph Theory and Computing (Arcata, Calif., Sept. 5-7). Humbolt State Univ. Congressus Numerant~um 26","year":"1979","author":"ALTON D. A.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"ARJOMANDI E. 1975. A study of parallelism in graph theory. Ph.D dissertation Dept. of Computer Science University of Toronto Toronto Ontario.   ARJOMANDI E. 1975. A study of parallelism in graph theory. Ph.D dissertation Dept. of Computer Science University of Toronto Toronto Ontario."},{"key":"e_1_2_1_4_1","unstructured":"ATALLAH M. J. 1983. Algorithms for VLSI networks of processors. Ph.D. dissertation Dept. of Electrical Engineering and Computer Science The Johns Hopkins Univ. Baltimore Md.   ATALLAH M. J. 1983. Algorithms for VLSI networks of processors. Ph.D. dissertation Dept. of Electrical Engineering and Computer Science The Johns Hopkins Univ. Baltimore Md."},{"key":"e_1_2_1_5_1","first-page":"345","volume-title":"Proceedings of the 14th Annual A CM Symposium on Theory o{ Computing","author":"ATALLAH M. J.","year":"1982"},{"key":"e_1_2_1_6_1","first-page":"307","volume-title":"Proceedings of the Spring Joint Computer Conference (Atlantic City, N.J., Apr. 30-May 2)","volume":"32","author":"BATCHER K. E.","year":"1968"},{"key":"e_1_2_1_7_1","first-page":"33","volume-title":"Infotech State of the Art Report: Supercomputers","volume":"2","author":"BATCHER K. E.","year":"1979"},{"key":"e_1_2_1_8_1","article-title":"Design of massively parallel processor","author":"TCHER K. E.","year":"1980","journal-title":"IEEE Trans Comput. C-29, 836- 840."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0196-6774(80)90004-8","article-title":"A parallel algorithm for constructing minimum spanning trees","author":"BENTLEY J. L.","year":"1980","journal-title":"J. Algorithms I, I (Mar.)"},{"key":"e_1_2_1_10_1","first-page":"257","volume-title":"Proceedings o{ the 1979 International Con{erence on Parallel Processing. IEEE","author":"B~NTLEY J. L","year":"1979"},{"key":"e_1_2_1_11_1","unstructured":"BERG H. K. BOEBERT W. E. FRANTA W. R. AND MOHER T. G. 1982. Formal Methods o{ Program Verifwation and Specification. Prentice- Hall Englewood Cliffs N.J. chap. 6.  BERG H. K. BOEBERT W. E. FRANTA W. R. AND MOHER T. G. 1982. Formal Methods o{ Program Verifwation and Specification. Prentice- Hall Englewood Cliffs N.J. chap. 6."},{"key":"e_1_2_1_12_1","first-page":"81","volume-title":"Md.","author":"BILARDI G.","year":"1981"},{"key":"e_1_2_1_13_1","unstructured":"BROWNINa S. A. 1980a. The tree machine: A highly concurrent computing environment. Ph.D. dissertation Dept. of Computer Science California Inst. of Technology Pasadena Calif.   BROWNINa S. A. 1980a. The tree machine: A highly concurrent computing environment. Ph.D. dissertation Dept. of Computer Science California Inst. of Technology Pasadena Calif."},{"volume-title":"Introduction to VLSI Systems","author":"BROWNING S. A.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_16_1","first-page":"98","volume-title":"Alternation. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science. IEEE","author":"CHANDRA A. K.","year":"1976"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/358690.358717"},{"key":"e_1_2_1_18_1","first-page":"318","volume-title":"Proceedings o{ the 13th Annual ACM Symposium on Theory of Computing (Milwaukee, Wis., May 11-13)","author":"CHAZELLE B.","year":"1981"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes m Computer Sciences","first-page":"306","volume-title":"Parallel Processing","author":"CHEN I.-N."},{"key":"e_1_2_1_20_1","first-page":"60","volume-title":"Proceedings of the 1973 Computer Conference on Parallel Processing (Sagamore, N.Y.)","author":"CHEN Y. K.","year":"1973"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1137\/0205051","article-title":"Finding mimmum spanning trees","volume":"5","author":"CHERITON D.","year":"1976","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_22_1","first-page":"170","volume-title":"Proceedings of the 1981 International Conference on Parallel Processing. iEEE","author":"CHIN F. Y.","year":"1981"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/358628.358650"},{"issue":"3","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","article-title":"An observation on time-storage trade-off","volume":"9","author":"COOK S. A.","year":"1974","journal-title":"J. Comput. Syst ScL"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1109\/TC.1968.227419","article-title":"Path finding with associative memory","volume":"7","author":"CRANE B. A.","year":"1968","journal-title":"IEEE Trans Comput. C-17"},{"key":"e_1_2_1_26_1","first-page":"57","volume-title":"R. R","author":"CRANE B. A.","year":"1972"},{"key":"e_1_2_1_27_1","first-page":"178","volume-title":"Proceedings o{ the 1982 International Conference on Parallel Processzng. IEEE","author":"DEKEL E.","year":"1982"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/opre.31.1.24","article-title":"Parallel scheduling algorithms","volume":"31","author":"DEKEL E","year":"1983","journal-title":"Oper Res."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1109\/TC.1983.1676223","article-title":"Binary trees and parallel scheduling algorithms","author":"DEKEL E.","year":"1983","journal-title":"IEEE Trans Comput. C-32, 3 (Mar.)"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1137\/0210049","article-title":"Parallel matrix and graph algorithms","volume":"10","author":"DEKEL E.","year":"1981","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_31_1","unstructured":"DENELCOR 1981. Heterogeneous element processor prmciples of operation. Publ. No. 9000001 HEP Technical Documentation Series Denelcor Inc. Denver Colo.  DENELCOR 1981. Heterogeneous element processor prmciples of operation. Publ. No. 9000001 HEP Technical Documentation Series Denelcor Inc. Denver Colo."},{"key":"e_1_2_1_32_1","unstructured":"DEO N. 1974. Graph Theory w~th Applications to Engineering and Computer Scasnce. Prentice- Hail New York.   DEO N. 1974. Graph Theory w~th Applications to Engineering and Computer Scasnce. Prentice- Hail New York."},{"key":"e_1_2_1_33_1","first-page":"188","volume-title":"Proceedings o{ the 1981 International Conference on Parallel Processing IEEE","author":"DEO N.","year":"1981"},{"key":"e_1_2_1_34_1","first-page":"244","volume-title":"Proceedings of the 1980 International Con\/erence on Parallel Processing. IEEE","author":"DEO N.","year":"1980"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"DIJKSTRA E. 1959. A note on two problems in connexion with graphs. Numer. Math i 269-271.  DIJKSTRA E. 1959. A note on two problems in connexion with graphs. Numer. Math i 269-271.","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"DOBKIN D. LIPTON R. J. AND REiSS S. 1979. Linear programming is log-space hard for P. Inf. Process Lett. '9 2 (Aug.) 6-97.  DOBKIN D. LIPTON R. J. AND REiSS S. 1979. Linear programming is log-space hard for P. Inf. Process Lett. '9 2 (Aug.) 6-97.","DOI":"10.1016\/0020-0190(79)90152-2"},{"key":"e_1_2_1_37_1","first-page":"360","volume-title":"Proceedings o{ the 21st Annual Symposium on Foundattons o{ Computing. IEEE","author":"DYMOND P. W.","year":"1980"},{"key":"e_1_2_1_41_1","first-page":"21","volume-title":"Proceedings o{ the Con{erence on Theoretical Computer Scasnce (Waterloo, Ontario, Aug.)","author":"ECKSTE N, D","year":"1977"},{"key":"e_1_2_1_42_1","first-page":"10","article-title":"Reaching for the gigaflop","volume":"13","author":"FALK H.","year":"1976","journal-title":"IEEE Spectrum"},{"key":"e_1_2_1_43_1","first-page":"77","volume-title":"Supercomputers","volume":"2","author":"FEIERBACH G.","year":"1979"},{"first-page":"113","volume-title":"High Speed Computer and Algorithm Organisation","author":"FLANDERS P. M.","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_46_1","first-page":"1901","volume-title":"Proc iEEE 54","author":"FLYNN M. J.","year":"1966"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/MC.1980.1653338","article-title":"Design of special-purpose VLSI chips--Example and opinions","volume":"13","author":"FOSTER M. J.","year":"1980","journal-title":"Computer"},{"key":"e_1_2_1_48_1","first-page":"358","volume-title":"Proceedings of the 13th IEEE Computer Society lnternatmnal Conference. IEEE","author":"FULLER S. H.","year":"1976"},{"key":"e_1_2_1_49_1","first-page":"203","volume-title":"Eds. Academic Press","author":"FUNG L.","year":"1977"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00263744","article-title":"Hierarchies of complete problems","volume":"6","author":"GALIL Z.","year":"1976","journal-title":"Acta Inf."},{"key":"e_1_2_1_51_1","first-page":"247","volume-title":"Proceedings of the 13th Annual ACM Sympostum on Theory of Computing (Milwaukee, Wis., May 11-13)","author":"GAUL Z.","year":"1981"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322382"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_2_1_54_1","unstructured":"GAREY M. R. AND JOHNSON D. S. 1979. Computers and Intractability: A Guide to the Theory of the NP-Completeness. Freeman San Francisco Calif.   GAREY M. R. AND JOHNSON D. S. 1979. Computers and Intractability: A Guide to the Theory of the NP-Completeness. Freeman San Francisco Calif."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322057"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1002\/nav.3800140304","article-title":"Maximum watching in a convex bipartite graph","volume":"14","author":"GLOVER F.","year":"1967","journal-title":"Naval Res Logist Q."},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/opre.28.3.694","article-title":"Approximate traveling salesman algorithms","volume":"28","author":"GOLDEN B.","year":"1980","journal-title":"Oper. Res."},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"GOLDSCHLAGER L. M. 1977a. The monotone and planar c~rcuit value problems are log space complete for P SIGACT News 9 2 (Summer) 25-29. 10.1145\/1008354.1008356   GOLDSCHLAGER L. M. 1977a. The monotone and planar c~rcuit value problems are log space complete for P SIGACT News 9 2 (Summer) 25-29. 10.1145\/1008354.1008356","DOI":"10.1145\/1008354.1008356"},{"key":"e_1_2_1_60_1","first-page":"89","volume-title":"New York","author":"GOLDSCHLAGER L. M.","year":"1978"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322353"},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","article-title":"The maximum flow problem is log space complete for P","volume":"21","author":"GOLDSCHLAGER L. M.","year":"1982","journal-title":"Theor Comput. Sci"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/359897.359904"},{"key":"e_1_2_1_64_1","first-page":"509","volume-title":"Proceedings of the Conference on Very Large Scale Integratton' Architecture, Design, Fabrwatlon (Pasadena, Calif., Jan.). California Institute of Technology, Pasadena, Calif.","author":"GUISAS L. J.","year":"1979"},{"key":"e_1_2_1_65_1","unstructured":"HAMBRUSCH S. E. 1982. The complexity of graph problems on VLSI. Ph.D. dissertation Computer Science Dept. The Pennsylvania State Univ. University Park Pa.   HAMBRUSCH S. E. 1982. The complexity of graph problems on VLSI. Ph.D. dissertation Computer Science Dept. The Pennsylvania State Univ. University Park Pa."},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1137\/0212023","article-title":"VLSI algorithms for the connected component problem","volume":"12","author":"HAMBRUSCH S. E.","year":"1983","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"HARARY F. 1969. Graph Theory. Addison-Wesley Reading Mass.  HARARY F. 1969. Graph Theory. Addison-Wesley Reading Mass.","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_68_1","first-page":"1385","volume-title":"Encyclopedia of Computer Sclence and Engineering","author":"HARRISON T. J.","edition":"2"},{"key":"e_1_2_1_69_1","first-page":"1","article-title":"A survey of highly parallel computing","volume":"14","author":"YNES L. S.","year":"1982","journal-title":"Computer"},{"key":"e_1_2_1_70_1","first-page":"287","volume-title":"IEEE","author":"HIGSIE L. C.","year":"1972"},{"key":"e_1_2_1_71_1","first-page":"55","volume-title":"Proceedings o{ the 8th Annual ACM Symposium on the Theory of Computing. ACM","author":"HIRSCHBERG D. S.","year":"1976"},{"key":"e_1_2_1_72_1","first-page":"257","volume-title":"Proceedings o{ the 20th AUerton Conference","author":"HIRSCHBERG D. S.","year":"1982"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359141"},{"volume-title":"Parallel Computers: Architecture, Programming, and Algortthms. Adam Hilger","year":"1981","author":"HOCKNE~ R. W.","key":"e_1_2_1_74_1"},{"issue":"4","key":"e_1_2_1_75_1","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF00998631","article-title":"Theoretical comparisons of search strategqes in branch-and-bound algorithms","volume":"5","author":"ISARAK","year":"1976","journal-title":"Int. J Comput Inf. Sci."},{"key":"e_1_2_1_76_1","first-page":"2","article-title":"Parallel algorithms in graph theory: Planarity testing","volume":"11","author":"JA'JA' J.","year":"1982","journal-title":"SIAM J. Cornput"},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0196-6774(83)90045-7","article-title":"The NP-completeness column: An ongoing guide","volume":"4","author":"JOHNSON D. S.","year":"1983","journal-title":"J. Algorithms"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/356810.356813"},{"issue":"1","key":"e_1_2_1_79_1","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","article-title":"Complete problems for deterministic polynomial time","volume":"3","author":"JONES N. D.","year":"1976","journal-title":"Theor. Comput. ScL"},{"key":"e_1_2_1_80_1","first-page":"37","volume-title":"Proceedings of the 22nd Annual Symposium on Foundations o{ Computer Science. IEEE","author":"KEDEM Z. M.","year":"1981"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360251"},{"key":"e_1_2_1_82_1","first-page":"231","volume-title":"Proceedings of the llth Annual ACM Symposium on Theory of Computing ACM","author":"KOSARAJU S. R.","year":"1979"},{"key":"e_1_2_1_83_1","first-page":"164","volume-title":"Proceedings of the 9th Annual A CM Symposium on Theory o{ Computing. ACM","author":"KOZEN D.","year":"1977"},{"key":"e_1_2_1_84_1","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest subtree of a graph and the traveling-s~lesman problem","volume":"7","author":"KRUSKAL J. B.","year":"1956","journal-title":"Proc Amer. Math. Soc"},{"key":"e_1_2_1_85_1","article-title":"Parallel computation and conflicts m memory access","volume":"14","author":"KU~ERA L.","year":"1982","journal-title":"Inf Process Lett."},{"key":"e_1_2_1_86_1","first-page":"65","volume-title":"Ed Academm Press","author":"KUN","year":"1980"},{"key":"e_1_2_1_87_1","doi-asserted-by":"crossref","unstructured":"KUNG H. T. 1982. Why systolic architectures~ Computer 15 1 (Jan.) 37-46.  KUNG H. T. 1982. Why systolic architectures~ Computer 15 1 (Jan.) 37-46.","DOI":"10.1109\/MC.1982.1653825"},{"first-page":"260","volume-title":"Introductton to VLSI Systems","author":"KUNG H. T.","key":"e_1_2_1_88_1"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/990518.990519"},{"key":"e_1_2_1_90_1","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1109\/TSE.1977.229904","article-title":"Proving the correctness of multlprocess programs","author":"LAMPORT L.","year":"1977","journal-title":"IEEE Trans Soft. Eng. SE-3, 7 (Mar.)"},{"volume-title":"L 1979. Proving the correctness of multlprocess programs. ACM Trans Progress Lang. Sys i, i (July), 86-97","author":"LAMPORT","key":"e_1_2_1_91_1"},{"key":"e_1_2_1_92_1","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1109\/T-C.1975.224157","article-title":"Access and alignment of data m an array processor","volume":"12","author":"LAWRIE D. H.","year":"1975","journal-title":"IEEE Trans Comput. C-24"},{"key":"e_1_2_1_93_1","first-page":"1","volume-title":"New York","author":"LEIGHTON F. T.","year":"1981"},{"key":"e_1_2_1_94_1","first-page":"270","volume-title":"Proceedings of the 21st Annual Symposmm on Foundations o{ Computer Science IEEE","author":"LEISERSON C. E.","year":"1980"},{"key":"e_1_2_1_95_1","unstructured":"LEmERSON C. E. 1983. Area-Effxient VLSI Computation MIT Press Cambridge Mass.   LEmERSON C. E. 1983. Area-Effxient VLSI Computation MIT Press Cambridge Mass."},{"key":"e_1_2_1_96_1","first-page":"23","volume-title":"Proceedings of the 22nd Annual Symposmm on Foundations of Computer Scaence. IEEE","author":"LEISERSON C. E.","year":"1981"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/361237.361240"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/361573.361576"},{"key":"e_1_2_1_99_1","doi-asserted-by":"crossref","unstructured":"LINT B. AND AGERWALA T. 1981 Communication issues in the design and analysis of parallel algorithms IEEE Trans Softw Eng. SE-7 2 (Mar.) 174-188.  LINT B. AND AGERWALA T. 1981 Communication issues in the design and analysis of parallel algorithms IEEE Trans Softw Eng. SE-7 2 (Mar.) 174-188.","DOI":"10.1109\/TSE.1981.230833"},{"key":"e_1_2_1_100_1","first-page":"13","volume-title":"Proceedings of the 22nd Annual Symposium on Foundatmns of Computer Science. IEEE","author":"LIPTON R J","year":"1981"},{"key":"e_1_2_1_101_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1287\/opre.11.6.972","article-title":"An algorithm for the traveling salesman problem","volume":"11","author":"LITTLE J. D.","year":"1963","journal-title":"Oper. Res"},{"key":"e_1_2_1_104_1","unstructured":"MEAD C. AND CONWAY L. 1980. Introduction to VLSI Systems Addmon-Wesley Reading Mass.   MEAD C. AND CONWAY L. 1980. Introduction to VLSI Systems Addmon-Wesley Reading Mass."},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357190"},{"key":"e_1_2_1_106_1","first-page":"191","volume-title":"Proceedings of the 1983 Internatlonal Conference on Parallel Processing IEEE","author":"MOHAN J.","year":"1983"},{"key":"e_1_2_1_107_1","unstructured":"MOORE E. F. 1957. The shortest path through a maze In Proceedings of the international Symposium on the Theory of Switching vol. 2 pp. 285-292.  MOORE E. F. 1957. The shortest path through a maze In Proceedings of the international Symposium on the Theory of Switching vol. 2 pp. 285-292."},{"key":"e_1_2_1_108_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TC.1979.1675216","article-title":"Bltonic sort on a mesh connected parallel computer","author":"NASS MI, D","year":"1979","journal-title":"IEEE Trans Comput. C-28, i"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1145\/322169.322172"},{"key":"e_1_2_1_110_1","first-page":"4","article-title":"Finding connected components and connected ones on a mesh-connected parallel computer","volume":"9","author":"NASS MI, D","year":"1980","journal-title":"SIAM J Comput"},{"key":"e_1_2_1_111_1","doi-asserted-by":"crossref","unstructured":"NATH D. AND MAHESHWARI S. N. 1982. Parallel algorithms for the connected components and minimal spanning tree problems. Inf. Process. Lett 14 1 (27 Mar.) 7-11.  NATH D. AND MAHESHWARI S. N. 1982. Parallel algorithms for the connected components and minimal spanning tree problems. Inf. Process. Lett 14 1 (27 Mar.) 7-11.","DOI":"10.1016\/0020-0190(82)90131-4"},{"key":"e_1_2_1_112_1","unstructured":"OLEINICK P. 1978. The implementation of parallel algorithms on an asynchronous multiprocessor. Ph.D. dissertation Dept. of Computer Science Carnegie-Mellon Univ. Pittsburgh Pa.  OLEINICK P. 1978. The implementation of parallel algorithms on an asynchronous multiprocessor. Ph.D. dissertation Dept. of Computer Science Carnegie-Mellon Univ. Pittsburgh Pa."},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/360051.360224"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357178"},{"key":"e_1_2_1_115_1","doi-asserted-by":"crossref","unstructured":"PAPE U. 1974. Implementation and efficiency of Moore-algorithms for the shortest route problem Math Program 7 2 (Oct.) 212-222.  PAPE U. 1974. Implementation and efficiency of Moore-algorithms for the shortest route problem Math Program 7 2 (Oct.) 212-222.","DOI":"10.1007\/BF01585517"},{"key":"e_1_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1145\/358645.358660"},{"key":"e_1_2_1_117_1","first-page":"363","volume-title":"Congressus Numerantium 34","author":"PRICE C. C.","year":"1982"},{"key":"e_1_2_1_119_1","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"PRIM R. C.","year":"1957","journal-title":"Bell Syst Tech J."},{"key":"e_1_2_1_120_1","unstructured":"QUINN M. J. 1983. The design and analysis of algorithms and data structures for the efficient solution of graph theoretic problems on MIMD computers. Ph.D. dissertation Computer Science Dept. Washington State Univ Pullman Wash.   QUINN M. J. 1983. The design and analysis of algorithms and data structures for the efficient solution of graph theoretic problems on MIMD computers. Ph.D. dissertation Computer Science Dept. Washington State Univ Pullman Wash."},{"key":"e_1_2_1_122_1","first-page":"311","volume-title":"S. F 1979 The DAP approach In Infotech State of the Art Report' Supercomputers","volume":"2","author":"REDOAWAY"},{"key":"e_1_2_1_123_1","first-page":"2","article-title":"Parallel computations in graph theory","volume":"2","author":"REGHBAT I), E","year":"1978","journal-title":"SIAM J. Comput"},{"key":"e_1_2_1_124_1","first-page":"201","volume-title":"Proceedings of the 14th Annual ACM Symposium on Theory o{ Computing","author":"REW J. H.","year":"1982"},{"key":"e_1_2_1_126_1","unstructured":"REINGOLD E. NiEVERGELT J. AND DEO N. 1977. Comblnatortal Algorithms Theory and Practzce Prentice-Hall New York.   REINGOLD E. NiEVERGELT J. AND DEO N. 1977. Comblnatortal Algorithms Theory and Practzce Prentice-Hall New York."},{"key":"e_1_2_1_127_1","first-page":"33","volume-title":"Proceedings of the 15th Annual iEEE Symposium on Switching and Automata Theory. IEEE","author":"ROSENKRANTZ D.","year":"1974"},{"key":"e_1_2_1_128_1","unstructured":"SAVAGE C. 1977. Parallel algorithms for graph theoretic problems Ph D. dissertation Mathematics Dept. Univ. of Illinois Urbana II1.  SAVAGE C. 1977. Parallel algorithms for graph theoretic problems Ph D. dissertation Mathematics Dept. Univ. of Illinois Urbana II1."},{"volume-title":"VLSI Systems and Computations, H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., Eds","author":"SAVAGE C.","key":"e_1_2_1_129_1"},{"key":"e_1_2_1_130_1","doi-asserted-by":"crossref","unstructured":"SAVAGE C. AND JA'JA' J. 1981. Fast efficient parallel algorithms for some graph problems. SIAM J Comput. I0 4 (Nov.) 682-690.  SAVAGE C. AND JA'JA' J. 1981. Fast efficient parallel algorithms for some graph problems. SIAM J Comput. I0 4 (Nov.) 682-690.","DOI":"10.1137\/0210051"},{"first-page":"61","volume-title":"VLSI Systems and Computations, H T. Kung, R F. Sproull, and G. Steele, Jr., Eds","author":"SAVAGE J.","key":"e_1_2_1_131_1"},{"key":"e_1_2_1_132_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"e_1_2_1_133_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"e_1_2_1_134_1","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1109\/TC.1979.1675280","article-title":"A model of SIMD machines and a comparison of various interconnection networks IEEE","volume":"12","author":"SIEGEL H. J.","year":"1979","journal-title":"Trans. Comput. C-28"},{"key":"e_1_2_1_135_1","first-page":"6","volume-title":"Proceedings of the 1978 International Conference on Parallel Processing. IEEE","author":"SMITH B. J.","year":"1978"},{"key":"e_1_2_1_136_1","unstructured":"SOLLIN M. 1977. An algorithm attributed to Sollin. In lntroductton to the Design and Analysis of Algorzthms S. E. Goodman and S. T. Hedetniemi Eds McGraw-Hill New York sect. 5.5.  SOLLIN M. 1977. An algorithm attributed to Sollin. In lntroductton to the Design and Analysis of Algorzthms S. E. Goodman and S. T. Hedetniemi Eds McGraw-Hill New York sect. 5.5."},{"key":"e_1_2_1_137_1","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1109\/T-C.1971.223205","article-title":"Parallel processing with the perfect shuffle","volume":"2","author":"STONE H S","year":"1971","journal-title":"IEEE Trans Comput. C-20"},{"key":"e_1_2_1_138_1","unstructured":"STONE H. S. 1980. Parallel computers. In lntroduct~on to Computer Architecture H. S. Stone Ed. Science Research Associates Chicago I11. chap. 8.  STONE H. S. 1980. Parallel computers. In lntroduct~on to Computer Architecture H. S. Stone Ed. Science Research Associates Chicago I11. chap. 8."},{"key":"e_1_2_1_139_1","first-page":"645","volume-title":"Proceedings of the National Computer Conference (Dallas, Tex., June 13-16)","volume":"46","author":"SWAN R. J.","year":"1977"},{"key":"e_1_2_1_140_1","first-page":"81","volume-title":"Proceedings of the 11th Annual ACM Symposium on Theory of Computing. ACM","author":"THOMPSON C. D.","year":"1979"},{"key":"e_1_2_1_141_1","unstructured":"THOMPSON C. D. 1980. A complexity theory for VLSi. Ph.D. dissertation Dept. of Computer Science Carnegie-Mellon Univ. Pittsburgh Pa.   THOMPSON C. D. 1980. A complexity theory for VLSi. Ph.D. dissertation Dept. of Computer Science Carnegie-Mellon Univ. Pittsburgh Pa."},{"key":"e_1_2_1_142_1","first-page":"58","volume-title":"Proceedings of the 8th Annual ACM Symposium on Theory of Computing. ACM","author":"THOMPSON C. D.","year":"1976"},{"key":"e_1_2_1_144_1","unstructured":"VAN ScoY F. L. 1976. Parallel algorithms in cellular spaces. Ph.D. dissertation School of Engineering and Applied Science Univ. of Virginia Charlottesville Va.   VAN ScoY F. L. 1976. Parallel algorithms in cellular spaces. Ph.D. dissertation School of Engineering and Applied Science Univ. of Virginia Charlottesville Va."},{"key":"e_1_2_1_145_1","first-page":"1","article-title":"Implementation of simultaneous memory access in models that forbid it","volume":"4","author":"VISHKIN U.","year":"1983","journal-title":"J. Algonthms"},{"key":"e_1_2_1_146_1","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1109\/TC.1983.1676221","article-title":"A combinatorial limit to the computing power of VLSI circuits","author":"VUILLEMIN J. E.","year":"1983","journal-title":"IEEE Trans. Comput C-32, 3 (Mar.)"},{"key":"e_1_2_1_147_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_2_1_148_1","doi-asserted-by":"publisher","DOI":"10.1145\/356707.356711"},{"key":"e_1_2_1_150_1","unstructured":"~VYLLIE J. C. 1979. The complexity of parallel computations. Ph.D. dissertation Dept. of Computer Science Cornell Univ. Ithaca N.Y.   ~VYLLIE J. C. 1979. The complexity of parallel computations. Ph.D. dissertation Dept. of Computer Science Cornell Univ. Ithaca N.Y."},{"key":"e_1_2_1_151_1","first-page":"1","article-title":"An O(IEI log log }V}) algorithm for finding minimum spanning trees","volume":"4","author":"YAO C.-C.","year":"1975","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_152_1","doi-asserted-by":"publisher","DOI":"10.1145\/356683.356685"},{"key":"e_1_2_1_153_1","unstructured":"Yoo Y. B. 1983. Parallel processing for some network optimization problems. Ph.D. dissertation Computer Science Dept. Washington State Univ. Pullman Wash.   Yoo Y. B. 1983. Parallel processing for some network optimization problems. Ph.D. dissertation Computer Science Dept. Washington State Univ. Pullman Wash."}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2514.2515","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2514.2515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:18Z","timestamp":1750235958000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2514.2515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,9,2]]},"references-count":141,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1984,9,2]]}},"alternative-id":["10.1145\/2514.2515"],"URL":"https:\/\/doi.org\/10.1145\/2514.2515","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[1984,9,2]]},"assertion":[{"value":"1984-09-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}