{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T04:45:59Z","timestamp":1693111559100},"reference-count":109,"publisher":"Elsevier","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1016\/s0065-2458(08)60006-6","type":"book-chapter","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T05:56:15Z","timestamp":1295416575000},"page":"93-153","source":"Crossref","is-referenced-by-count":7,"title":["Parallel Algorithms for Some Computational Problems"],"prefix":"10.1016","author":[{"given":"Abha","family":"Moitra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Sitharama Iyengar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0065-2458(08)60006-6_bib1","series-title":"\u201cThe Design and Analysis of Computer Algorithms\u201d","author":"Aho","year":"1974"},{"key":"10.1016\/S0065-2458(08)60006-6_bib2","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1109\/TPAMI.1982.4767226","article-title":"Design, analysis and implementation of a parallel tree search algorithm","volume":"PAMI-4","author":"Akl","year":"1982","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10.1016\/S0065-2458(08)60006-6_bib3","unstructured":"E. Arjomandi D.G. Corneil (1975) Parallel computations in graph theory. Proc. 16th Annu. Symp. Foundations Comput. Sci., 13-18"},{"key":"10.1016\/S0065-2458(08)60006-6_bib4","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90072-3","article-title":"Parallel strong orientation of an undirected graph","volume":"18","author":"Atallah","year":"1984","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib5","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1109\/TC.1985.1676551","article-title":"A generalized dictionary machine for VLSI","volume":"C-35","author":"Atallah","year":"1985","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib6","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/0022-0000(84)90003-5","article-title":"Finding Euler tours in parallel","volume":"29","author":"Atallah","year":"1984","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0065-2458(08)60006-6_bib7","unstructured":"B. Awerbuch Y. Shiloach (1983) New connectivity and MSF algorithms for Ultracomputer and PRAM. Proc. 1983 Int. Conf. Parallel Process., 175-179"},{"key":"10.1016\/S0065-2458(08)60006-6_bib8","unstructured":"B. Awerbuch A. Israeli Y. Shiloach (1984) Finding Euler circuits in logarithmic parallel time. Proc. 16th Annu. ACM Symp. Theory Comput., 249-257"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib9","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1145\/3318.3478","article-title":"Optimal parallel generation of a computation tree form","volume":"7","author":"Bar-On","year":"1985","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"10.1016\/S0065-2458(08)60006-6_bib10","series-title":"The design and analysis of algorithms for asynchronous multiprocessors","author":"Baudet","year":"1978"},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib11","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","volume":"1","author":"Bentley","year":"1980","journal-title":"J. Algorithms"},{"key":"10.1016\/S0065-2458(08)60006-6_bib12","unstructured":"J.L. Bentley H.T. Kung (1979) A tree machine for searching problems. Proc. 1979 Int. Conf. Parallel Process., 256-266"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0004-3702(78)80012-5","article-title":"A chronology of computer chess and its literature","volume":"10","author":"Berliner","year":"1978","journal-title":"Artif. Intell."},{"key":"10.1016\/S0065-2458(08)60006-6_bib14","series-title":"Parallel polynomial division can be accelerated preserving full efficiency of the best sequential algorithms","author":"Bini","year":"1985"},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/2514.2516","article-title":"A taxonomy of parallel sorting","volume":"16","author":"Bitton","year":"1984","journal-title":"ACM Comput. Surv."},{"key":"10.1016\/S0065-2458(08)60006-6_bib16","unstructured":"A.K. Chandra (1976) Maximal parallelism in matrix multiplication. IBM Tech. Rep. RC 6193, Thomas J. Watson Research Center, Yorktown Heights, N.Y"},{"key":"10.1016\/S0065-2458(08)60006-6_bib17","series-title":"Speedups of iterative programs in multiprocessing systems","author":"Chen","year":"1975"},{"issue":"4","key":"10.1016\/S0065-2458(08)60006-6_bib18","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1137\/0205051","article-title":"Finding minimum spanning trees","volume":"5","author":"Cheriton","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib19","unstructured":"F.Y. Chin J. Lam I.-N. Chen (1981) Optimal parallel algorithms for the connected component problem. Proc. 1981 Int. Conf. Parallel Process., 170-175"},{"issue":"9","key":"10.1016\/S0065-2458(08)60006-6_bib20","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1145\/358628.358650","article-title":"Efficient parallel algorithms for some graph problems","volume":"25","author":"Chin","year":"1982","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60006-6_bib21","first-page":"99","article-title":"Towards a complexity theory of synchronous parallel computation","volume":"XXVII","author":"Cook","year":"1981","journal-title":"L'Enseignement Mathematique"},{"issue":"4","key":"10.1016\/S0065-2458(08)60006-6_bib22","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","article-title":"Fast parallel inversion algorithms","volume":"5","author":"Csanky","year":"1976","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib23","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1109\/TC.1983.1676223","article-title":"Binary trees and parallel scheduling algorithms","volume":"C-32","author":"Dekel","year":"1983","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib24","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/2166.357211","article-title":"Parallel generation of postfix and tree forms","volume":"5","author":"Dekel","year":"1983","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"10.1016\/S0065-2458(08)60006-6_bib25","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","article-title":"A parallel matching algorithm for convex bipartite graphs and applications to scheduling","volume":"1","author":"Dekel","year":"1984","journal-title":"J. Parallel Distrib. Comput."},{"issue":"4","key":"10.1016\/S0065-2458(08)60006-6_bib26","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1137\/0210049","article-title":"Parallel matrix and graph algorithms","volume":"10","author":"Dekel","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib27","unstructured":"E. Dekel S. Peng S.S. Iyengar (1985) Optimal parallel algorithm for constructing and maintaining a balanced m-way search tree. Tech. Rep. CS-209, Dept. Mathematical Sciences, Univ. Texas at Dallas. Dallas, Texas"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib28","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/net.3230140208","article-title":"Shortest path algorithms: Taxonomy and annotation","volume":"14","author":"Deo","year":"1984","journal-title":"Networks"},{"key":"10.1016\/S0065-2458(08)60006-6_bib29","unstructured":"N. Deo Y.B. Yoo (1981) Parallel algorithms for the minimum spanning tree problem. Proc. 1981 Int. Conf. Parallel Process., 188-189"},{"key":"10.1016\/S0065-2458(08)60006-6_bib30","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"10.1016\/S0065-2458(08)60006-6_bib31","series-title":"Simultaneous memory access","author":"Eckstein","year":"1979"},{"key":"10.1016\/S0065-2458(08)60006-6_bib32","series-title":"BFS and biconnectivity","author":"Eckstein","year":"1979"},{"key":"10.1016\/S0065-2458(08)60006-6_bib33","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0004-3702(82)90022-4","article-title":"Parallelism in alpha-beta search","volume":"19","author":"Finkel","year":"1982","journal-title":"Artif. Intell."},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib34","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1109\/TPAMI.1983.4767350","article-title":"Improved speedup bounds for parallel alpha-beta search IEEE Trans","volume":"PAMI-5","author":"Finkel","year":"1983","journal-title":"Pattern Anal. Mach. Intell."},{"key":"10.1016\/S0065-2458(08)60006-6_bib35","doi-asserted-by":"crossref","unstructured":"A.L. Fisher (1984) Dictionary machines with a small number of processors. Proc. 11th Annu. ACM Conf. Comput. Architecture,154-156","DOI":"10.1145\/800015.808177"},{"issue":"6","key":"10.1016\/S0065-2458(08)60006-6_bib36","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60006-6_bib37","doi-asserted-by":"crossref","unstructured":"Z. Galil (1984) Optimal parallel algorithms for string matching. Proc. 16th Annu. ACM Symp. Theory Comput., 240-248","DOI":"10.1145\/800057.808687"},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib38","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1145\/322047.322057","article-title":"Some complexity results for matrix computations on parallel processors","volume":"25","author":"Gentleman","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60006-6_bib39","first-page":"193","article-title":"Parallel algorithms for connectivity problems in graph theory","volume":"18","author":"Ghosh","year":"1986","journal-title":"J. Comput. Math."},{"key":"10.1016\/S0065-2458(08)60006-6_bib40","doi-asserted-by":"crossref","unstructured":"D.S. Hirschberg (1976) Parallel algorithms for the transitive closure and the connected component problems. Proc. 8th Annu. ACM Symp. Theory Comput., 55-57","DOI":"10.1145\/800113.803631"},{"issue":"8","key":"10.1016\/S0065-2458(08)60006-6_bib41","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1145\/359576.359582","article-title":"Fast parallel sorting algorithms","volume":"21","author":"Hirschberg","year":"1978","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60006-6_bib42","unstructured":"D.S. Hirschberg (1982) Parallel graph algorithms without memory conflicts. Proc. 20th Allerton Conf., 257-263"},{"key":"10.1016\/S0065-2458(08)60006-6_bib43","unstructured":"D.S. Hirschberg D.J. Volper (1983) A parallel solution for the minimum spanning tree problem. Proc. 17th Annu. Conf. Inf. Sci. Syst., 680-684"},{"issue":"8","key":"10.1016\/S0065-2458(08)60006-6_bib44","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/359138.359141","article-title":"Computing connected components on parallel computers","volume":"22","author":"Hirschberg","year":"1979","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60006-6_bib45","series-title":"\u201cFundamentals of Data Structures\u201d","author":"Horowitz","year":"1976"},{"key":"10.1016\/S0065-2458(08)60006-6_bib46","doi-asserted-by":"crossref","unstructured":"L. Hyafil (1978) On the parallel evaluation of the multivariate polynomials. Proc. 10th Annu. ACM Symp. Theory Comput., 193-195","DOI":"10.1145\/800133.804347"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib47","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1137\/0211024","article-title":"Parallel algorithms in graph theory: Planarity testing","volume":"11","author":"Ja'Ja'","year":"1982","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/S0065-2458(08)60006-6_bib48","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","article-title":"A fast parallel algorithm for the maximal independent set problem","volume":"32","author":"Karp","year":"1985","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60006-6_bib49","unstructured":"R.M. Karp E. Upfal A. Wigderson (1985) Constructing a perfect matching in random NC. Proc. 17th Annu. ACM Symp. Theory Comput., 22-32"},{"key":"10.1016\/S0065-2458(08)60006-6_bib50","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321765.321782","article-title":"Parallel program schemata and maximal parallelism I: Fundamental results","volume":"20","author":"Keller","year":"1973","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"10.1016\/S0065-2458(08)60006-6_bib51","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0004-3702(75)90019-3","article-title":"An analysis of alpha-beta pruning","volume":"6","author":"Knuth","year":"1975","journal-title":"Artif. Intell."},{"key":"10.1016\/S0065-2458(08)60006-6_bib52","unstructured":"D. Kozen U.V. Vazirani V.V. Vazirani (1985) NC algorithms for comparability graphs, interval graphs and testing for unique perfect matching. Fifth Conf. Foundations Software Tech. and Theoretical Comp. Sci., 496-503"},{"key":"10.1016\/S0065-2458(08)60006-6_bib53","series-title":"\u201cAlgorithms: Their Complexity and Efficiency\u201d","author":"Kronsjo","year":"1979"},{"key":"10.1016\/S0065-2458(08)60006-6_bib54","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 salesman problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib55","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","article-title":"Parallel computation and conflicts in memory access","volume":"14","author":"Kucera","year":"1982","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/S0065-2458(08)60006-6_bib56","article-title":"Parallel processing of ordinary programs","volume":"15","author":"Kuck","year":"1976"},{"key":"10.1016\/S0065-2458(08)60006-6_bib57","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/356683.356686","article-title":"A survey of parallel machine organization and programming","volume":"9","author":"Kuck","year":"1977","journal-title":"ACM Comput. Surv."},{"key":"10.1016\/S0065-2458(08)60006-6_bib58","series-title":"\u201cTutorial on Parallel Processing\u201d","author":"Kuhn","year":"1981"},{"issue":"6","key":"10.1016\/S0065-2458(08)60006-6_bib59","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1109\/TPAMI.1984.4767600","article-title":"Parallel branch and bound formulations for understanding and synthesising AND\/OR TREE search","volume":"PAMI-6","author":"Kumar","year":"1984","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10.1016\/S0065-2458(08)60006-6_bib60","article-title":"The structure of parallel algorithms","volume":"19","author":"Kung","year":"1980"},{"key":"10.1016\/S0065-2458(08)60006-6_bib61","unstructured":"S.C. Kwan W.L. Ruzzo (1984) Adaptive parallel algorithms for finding minimum spanning trees. Proc. 1984 Int. Conf. Parallel Process., 439-443"},{"key":"10.1016\/S0065-2458(08)60006-6_bib62","article-title":"Parallel sorting algorithms","volume":"23","author":"Lakshmivarahan","year":"1984"},{"issue":"10","key":"10.1016\/S0065-2458(08)60006-6_bib63","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1109\/TC.1985.6312196","article-title":"Am empirical study of automatic restructuring of nonnumerical programs for parallel processors","volume":"C-34","author":"Lee","year":"1985","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib64","series-title":"Systolic priority queues","author":"Leiserson","year":"1979"},{"issue":"9","key":"10.1016\/S0065-2458(08)60006-6_bib65","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1145\/361573.361576","article-title":"Cellular arrays for the solution of graph problems","volume":"15","author":"Levitt","year":"1972","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60006-6_bib66","doi-asserted-by":"crossref","unstructured":"M. Luby (1985) A simple parallel algorithm for the maximal independent set problem. Proc. 17th Annu. ACM Symp. Theory Comput., 1-10","DOI":"10.1145\/22145.22146"},{"key":"10.1016\/S0065-2458(08)60006-6_bib67","series-title":"Parallel algorithms for the single source shortest path problems","author":"Mateti","year":"1981"},{"key":"10.1016\/S0065-2458(08)60006-6_bib68","series-title":"\u201cIntroduction to VLSI Systems\u201d","author":"Mead","year":"1980"},{"key":"10.1016\/S0065-2458(08)60006-6_bib69","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0167-6423(85)90016-4","article-title":"Automatic construction of CSP programs from sequential nondeterministic programs","volume":"5","author":"Moitra","year":"1986","journal-title":"Sci. Comput. Program."},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib70","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1109\/TSE.1986.6312885","article-title":"Derivation of a parallel algorithm for balancing binary trees","volume":"SE-12","author":"Moitra","year":"1986","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0065-2458(08)60006-6_bib71","doi-asserted-by":"crossref","unstructured":"K. Mulmuley U.V. Vazirani V.V. Vazirani (1986) Matching is as easy as matrix inversion. To appear in Combinatorics","DOI":"10.1145\/28395.383347"},{"key":"10.1016\/S0065-2458(08)60006-6_bib72","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0022-0000(73)80043-1","article-title":"Optimal algorithms for polynomial evaluations","volume":"7","author":"Munro","year":"1973","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib73","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(82)90131-4","article-title":"Parallel algorithms for the connected components and minimal spanning tree problems","volume":"14","author":"Nath","year":"1982","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/S0065-2458(08)60006-6_bib74","unstructured":"A. Nicolau (1985) Uniform parallelism exploitation in ordinary programs. Proc. 1985 IEEE Int. Conf. Parallel Process., 614-618"},{"key":"10.1016\/S0065-2458(08)60006-6_bib75","series-title":"\u201cPrinciples of Artificial Intelligence\u201d","author":"Nilsson","year":"1980"},{"issue":"9","key":"10.1016\/S0065-2458(08)60006-6_bib76","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/TC.1982.1676104","article-title":"A dictionary machine for VLSI","volume":"C-31","author":"Ottaman","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib77","unstructured":"R.C. Paige C.P. Kruskal (1985) Parallel algorithms for shortest path problems. Proc. 1985 IEEE Int. Conf. Parallel Process., 14-20"},{"key":"10.1016\/S0065-2458(08)60006-6_bib78","series-title":"Complexity of computing polynomial zeros","author":"Pan","year":"1985"},{"key":"10.1016\/S0065-2458(08)60006-6_bib79","series-title":"Improving the efficiency of parallel algorithms for the evaluation of the determinant and of the inverse of a matrix","author":"Pan","year":"1985"},{"issue":"8","key":"10.1016\/S0065-2458(08)60006-6_bib80","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1145\/358589.358616","article-title":"The solution for the branching factor of alpha-beta pruning algorithms and its optimality","volume":"25","author":"Pearl","year":"1982","journal-title":"Commun. ACM"},{"issue":"7","key":"10.1016\/S0065-2458(08)60006-6_bib81","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1109\/TC.1978.1675167","article-title":"New parallel sorting schemes","volume":"C-27","author":"Preparata","year":"1973","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib82","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","year":"1957","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib83","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/2514.2515","article-title":"Parallel graph algorithms","volume":"16","author":"Quinn","year":"1984","journal-title":"ACM Comput. Surv."},{"key":"10.1016\/S0065-2458(08)60006-6_bib84","series-title":"Maximum matchings in general graphs through randomization","author":"Rabin","year":"1984"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib85","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0207020","article-title":"Parallel computations in graph theory","volume":"2","author":"Reghbati Arjomandi","year":"1978","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10.1016\/S0065-2458(08)60006-6_bib86","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","article-title":"Depth-first search is inherently sequential","volume":"20","author":"Reif","year":"1985","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/S0065-2458(08)60006-6_bib87","series-title":"\u201cTutorial on Parallel Processing\u201d","first-page":"412","article-title":"Numerical parallel algorithms\u2014A survey","author":"Sameh","year":"1977"},{"key":"10.1016\/S0065-2458(08)60006-6_bib88","series-title":"Parallel algorithms for graph theoretic problems","author":"Savage","year":"1977"},{"issue":"4","key":"10.1016\/S0065-2458(08)60006-6_bib89","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1137\/0210051","article-title":"Fast, efficient parallel algorithms for some graph problems","volume":"10","author":"Savage","year":"1981","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib90","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","article-title":"An O(log n) parallel connectivity algorithm","volume":"3","author":"Shiloach","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/S0065-2458(08)60006-6_bib91","unstructured":"L. Shrira N. Francez M. Rodeh (1983) Distributed k-selection : From a sequential to a distributed algorithm. Proc. Second Annu. ACM Symp. Principles of Distributed Computing, ACM, New York, 143-153"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib92","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1145\/321510.321511","article-title":"Experiments with some programs that search game trees","volume":"16","author":"Slagle","year":"1969","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60006-6_bib93","series-title":"\u201cIntroduction to the Design and Analysis of Algorithms\u201d","article-title":"An algorithm attributed to Sollin","author":"Sollin","year":"1977"},{"key":"10.1016\/S0065-2458(08)60006-6_bib94","unstructured":"A.K. Somani V.K. Agarwal (1984) An efficient VLSI dictionary machine. Proc. 11th Annu. ACM Int. Symp. Comput. Architecture, 142-150"},{"key":"10.1016\/S0065-2458(08)60006-6_bib95","series-title":"\u201cIntroduction to Computer Architecture\u201d","article-title":"Parallel computers","author":"Stone","year":"1980"},{"key":"10.1016\/S0065-2458(08)60006-6_bib96","unstructured":"R. Strom S. Yemini (1985) Synthesizing distributed and parallel programs through optimistic transformations. Proc. 1985 IEEE Int. Conf. Parallel Process., 632-642"},{"key":"10.1016\/S0065-2458(08)60006-6_bib97","unstructured":"Y. Tanaka Y. Nozoka A. Masuyama (1980) Pipeline searching and sorting modules as components of data flow database computer. Proc. IFIP, 427-432"},{"issue":"2","key":"10.1016\/S0065-2458(08)60006-6_bib98","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib99","unstructured":"R.E. Tarjan U. Vishkin (1984) Finding biconnected components and computing tree functions in logarithmic parallel time. Proc. 25th Annu. Symp. Foundations of Comput. Sci., 12-20"},{"issue":"3","key":"10.1016\/S0065-2458(08)60006-6_bib100","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1137\/0213036","article-title":"Efficient parallel algorithms for a class of graph theoretic problems","volume":"13","author":"Tsin","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib101","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","article-title":"The factorization of linear graphs","volume":"22","author":"Tutte","year":"1947","journal-title":"J. London Math. Soc."},{"key":"10.1016\/S0065-2458(08)60006-6_bib102","unstructured":"L.G. Valiant (1982) Parallel computation. Proc. 7th IBM Symp. Math. Foundations of Comput. Sci"},{"key":"10.1016\/S0065-2458(08)60006-6_bib103","article-title":"Fast parallel computation of polynomials using few processors","volume":"118","author":"Valiant","year":"1981"},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib104","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0196-6774(83)90033-0","article-title":"Implementation of simultaneous memory address access in models that forbid it","volume":"4","author":"Vishkin","year":"1983","journal-title":"J. Algorithms"},{"key":"10.1016\/S0065-2458(08)60006-6_bib105","article-title":"Optimal parallel pattern matching in strings","volume":"194","author":"Vishkin","year":"1985"},{"issue":"5","key":"10.1016\/S0065-2458(08)60006-6_bib106","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1109\/TC.1986.1676783","article-title":"New classes for parallel complexity : A study of unification and other complete problems in P","volume":"C-35","author":"Vitter","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60006-6_bib107","series-title":"The complexity of parallel computations","author":"Wyllie","year":"1979"},{"issue":"1","key":"10.1016\/S0065-2458(08)60006-6_bib108","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(75)90056-3","article-title":"An O(|E|log log|V|) algorithm for finding minimum spaning trees","volume":"4","author":"Yao","year":"1975","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/S0065-2458(08)60006-6_bib109","series-title":"Parallel processing for some network optimization problems","author":"Yoo","year":"1983"}],"container-title":["Advances in Computers","Advances in Computers Volume 26"],"original-title":[],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T23:46:56Z","timestamp":1559951216000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0065245808600066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"references-count":109,"URL":"https:\/\/doi.org\/10.1016\/s0065-2458(08)60006-6","relation":{},"ISSN":["0065-2458"],"issn-type":[{"value":"0065-2458","type":"print"}],"subject":[],"published":{"date-parts":[[1987]]}}}