{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:44Z","timestamp":1742617124633,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":119,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_148","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:37:24Z","timestamp":1330209444000},"page":"363-380","source":"Crossref","is-referenced-by-count":9,"title":["Structural parallel algorithmics"],"prefix":"10.1007","author":[{"given":"Uzi","family":"Vishkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7:567\u2013583, 1986.","journal-title":"J. Algorithms"},{"key":"28_CR2","unstructured":"K. Abrahamson, N. Dadoun, D. A. Kirkpatrick, and T. Przytycka. A simple parallel tree contraction algorithm. Technical Report 87-30, The University of British Columbia, 1987."},{"key":"28_CR3","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, MA, 1974."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Israeli, and Y. Shiloach. Finding Euler circuits in logarithmic parallel time. In Proc. of the 16th Ann. ACM Symp. on Theory of Computing, pages 249\u2013257, May 1984.","DOI":"10.1145\/800057.808688"},{"key":"28_CR5","volume-title":"The Design and Analysis of Parallel Algorithms","author":"S.G. Akl","year":"1989","unstructured":"S.G. Akl. The Design and Analysis of Parallel Algorithms. Prentice Hall, Engelwood Cliffs, New Jersey, 1989."},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. An O(n log n) sorting network. In Proc. of the 15th Ann. ACM Symp. on Theory of Computing, pages 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"28_CR7","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BFb0040376","volume":"319","author":"R.J. Anderson","year":"1988","unstructured":"R.J. Anderson and G.L. Miller. Optimal parallel algorithms for list ranking. In 3rd Aegean workshop on computing, Lecture Notes in Computer Science 319, 1988 Springer-Verlag, pages 81\u201390, 1988.","journal-title":"Lecture Notes in Computer Science"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"N. Alon and N. Megiddo. Parallel linear programming almost surely in constant time. In Proc. of the 31st IEEE Annual Symp. on Foundation of Computer Science, pages 574\u2013582, 1990.","DOI":"10.1109\/FSCS.1990.89578"},{"key":"28_CR9","first-page":"192","volume":"447","author":"M.J. Atallah","year":"1990","unstructured":"M.J. Atallah. A faster algorithm for a parallel algorithm for a matrix searching problem. In Proc. 2nd SWAT, volume LNCS 447, pages 192\u2013200. Springer-Verlag, 1990.","journal-title":"LNCS"},{"key":"28_CR10","unstructured":"M.J. Atallah. Parallel techniques for computational geometry. Technical Report CS-1020, Purdue University, 1990."},{"issue":"3","key":"28_CR11","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/0022-0000(84)90003-5","volume":"29","author":"M.J. Atallah","year":"1984","unstructured":"M.J. Atallah and U. Vishkin. Finding Euler tours in parallel. J. Comp. Sys. Sci., 29,3:330\u2013337, 1984.","journal-title":"J. Comp. Sys. Sci."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"K. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, pages 307\u2013314, 32(1968).","DOI":"10.1145\/1468075.1468121"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"O. Berkman, D. Breslauer, Z. Galil, B. Schieber, and U. Vishkin. Highly-parallelizable problems. In Proc. of the 21st Ann. ACM Symp. on Theory of Computing, pages 309\u2013319, 1989.","DOI":"10.1145\/73007.73036"},{"key":"28_CR14","unstructured":"P.C.P. Bhatt, K. Diks, T. Hagerup, V.C. Prasad, T. Radzik, and S. Saxena. Improved deterministic parallel integer sorting. Technical Report TR 15\/1989, Fachbereich Informatik, Universit\u00e4t des Saarlandes, D-6600 Saarbr\u00fccken, W. Germany, November 1989."},{"key":"28_CR15","unstructured":"D. Breslauer and Z. Galil. An optimal O(log log n) parallel string matching algorithm. To appear in SIAM J. Comput., 1988."},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"D. Breslauer and Z. Galil. A lower bound for parallel string matching. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, 1991.","DOI":"10.1145\/103418.103465"},{"key":"28_CR17","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(85)90008-X","volume":"30","author":"A. Borodin","year":"1985","unstructured":"A. Borodin and J.E. Hopcroft. Routing, merging, and sorting on parallel models of computation. J. Computer and System Sciences, 30:130\u2013145, 1985.","journal-title":"J. Computer and System Sciences"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"P. Beame and J. Hastad. Optimal bounds for decision problems on the CRCW PRAM. In Proc. of the 19th Ann. ACM Symp. on Theory of Computing, pages 83\u201393, 1987.","DOI":"10.1145\/28395.28405"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"O. Berkman, J. J\u00e1J\u00e1, S. Krishnamurthy, R. Thurimella, and U. Vishkin. Some triply-logarithmic parallel algorithms. In Proc. of the 31st IEEE Annual Symp. on Foundation of Computer Science, pages 871\u2013881, 1990.","DOI":"10.1109\/FSCS.1990.89611"},{"key":"28_CR20","unstructured":"O. Berkman, J. J\u00e1J\u00e1, S. Krishnamurthy, R. Thurimella, and U. Vishkin. Top-bottom routing is as easy as prefix minima. In preparation (a preliminary and partial version is part of Some Triply-logarithmic Parallel Algorithms, see above), 1991."},{"key":"28_CR21","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0218014","volume":"18","author":"G. Bilardi","year":"1989","unstructured":"G. Bilardi and A. Nicolau. Adaptive bitonic sorting: an optimal parallel algorithm for sharedmemory machines. SIAM J. Computing, 18:216\u2013228, 1989.","journal-title":"SIAM J. Computing"},{"key":"28_CR22","doi-asserted-by":"crossref","first-page":"302","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:302\u2013206, 1974.","journal-title":"J. Assoc. Comput. Mach."},{"key":"28_CR23","unstructured":"O. Berkman, B. Schieber, and U. Vishkin. Some doubly logarithmic parallel algorithms based on finding all nearest smaller values. Technical Report UMIACS-TR-88-79, Univ. of Maryland Inst. for Advanced Computer Studies, 1988."},{"key":"28_CR24","unstructured":"O. Berkman, B. Schieber, and U. Vishkin. The parallel complexity of finding the convex hull of a monotone polygon. In preparation, 1991."},{"key":"28_CR25","doi-asserted-by":"crossref","unstructured":"O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 196\u2013202, 1989.","DOI":"10.1109\/SFCS.1989.63478"},{"key":"28_CR26","unstructured":"O. Berkman and U. Vishkin. On parallel integer merging. Technical Report UMIACS-TR-90-15, University of Maryland Inst. for Advanced Computer Studies, 1990."},{"key":"28_CR27","unstructured":"O. Berkman and U. Vishkin. Almost fully-parallel paretheses matching. In preparation, 1991."},{"key":"28_CR28","unstructured":"O. Berkman and U. Vishkin. Finding level-ancestors in trees. Technical Report UMIACS-TR-91-9, University of Maryland Institute for Advanced Computer Studies, 1991."},{"key":"28_CR29","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S.A. Cook","year":"1986","unstructured":"S.A. Cook, C. Dwork, and R. Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput., 15:87\u201397, 1986.","journal-title":"SIAM J. Comput."},{"key":"28_CR30","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, S. Fortune, and R.J. Lipton. Unbounded fan-in circuits and associative functions. In Proc. of the 15th Ann. ACM Symp. on Theory of Computing, pages 52\u201360, 1983.","DOI":"10.1145\/800061.808732"},{"key":"28_CR31","doi-asserted-by":"crossref","unstructured":"S. Chaudhuri. Tight bounds for the chaining problem. preprint, December, 1990.","DOI":"10.1145\/113379.113385"},{"issue":"4","key":"28_CR32","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM J. Computing, 17(4):770\u2013785, 1988.","journal-title":"SIAM J. Computing"},{"key":"28_CR33","first-page":"99","volume":"27","author":"S.A. Cook","year":"1981","unstructured":"S.A. Cook. Towards a complexity theory of synchronous parallel computation. Ensign. Math. 27:99\u2013124, 1981.","journal-title":"Ensign. Math."},{"key":"28_CR34","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"28_CR35","doi-asserted-by":"crossref","unstructured":"J. Cheriyan and R. Thurimella. Algorithms for parallel k-vertex connectivity and sparse certificates. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, 1991.","DOI":"10.1145\/103418.103460"},{"key":"28_CR36","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to list, tree and graph problems. In Proc. of the 27th IEEE Annual Symp. on Foundation of Computer Science, pages 478\u2013491, 1986.","DOI":"10.1109\/SFCS.1986.10"},{"key":"28_CR37","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70:32\u201353, 1986.","journal-title":"Information and Control"},{"key":"28_CR38","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF01762121","volume":"3","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3:329\u2013348, 1988.","journal-title":"Algorithmica"},{"key":"28_CR39","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin. Faster optimal parallel prefix sums and list ranking. Information and Computation, 81:334\u2013352, 1989.","journal-title":"Information and Computation"},{"key":"28_CR40","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/0743-7315(90)90103-V","volume":"8","author":"R. Cole","year":"1990","unstructured":"R. Cole and O. Zajicek. An optimal parallel algorithm for building a data structure for planar point location. J. Parallel and Distributed Computing, 8:280\u2013285, 1990.","journal-title":"J. Parallel and Distributed Computing"},{"key":"28_CR41","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. An optimal parallel dictionary. In Proc. 1st ACM Symposium on Parallel Algorithms and Architectures, pages 360\u2013368, 1989.","DOI":"10.1145\/72935.72974"},{"key":"28_CR42","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D. Eppstein","year":"1988","unstructured":"D. Eppstein and Z. Galil. Parallel algorithmic techniques for combinatorial computation. Ann. Rev. Comput. Sci., 3:233\u2013283, 1988.","journal-title":"Ann. Rev. Comput. Sci."},{"key":"28_CR43","first-page":"379","volume":"372","author":"D. Fussell","year":"1989","unstructured":"D. Fussell, V.L. Ramachandran, and R. Thurimella. Finding triconnected components by local replacements. In Proc. of 16th ICALP, Springer LNCS 372, pages 379\u2013393, 1989.","journal-title":"LNCS"},{"key":"28_CR44","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie. Parallelism in random access machines. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pages 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"key":"28_CR45","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Z. Galil. Optimal parallel algorithms for string matching. Information and Control, 67:144\u2013157, 1985.","journal-title":"Information and Control"},{"key":"28_CR46","doi-asserted-by":"crossref","unstructured":"H. Gazit. An optimal randomized parallel algorithm for finding connected components in a graph. In Proc. of the 27th IEEE Annual Symp. on Foundation of Computer Science, pages 492\u2013501, 1986.","DOI":"10.1109\/SFCS.1986.9"},{"key":"28_CR47","unstructured":"J. Gil. Fast load balancing on PRAM. Preliminary report; see also: Lower Bounds and Algorithms for Hashing and Parallel Processing, Ph.D. Thesis, Hebrew University, Jerusalem, Israel, 1990."},{"key":"28_CR48","unstructured":"J. Gil and Y. Matias. Fast hashing on a PRAM. In Proc. of the 2nd Second ACM-SIAM Symposium on Discrete Algorithms, pages 271\u2013280, 1991."},{"key":"28_CR49","unstructured":"Y. Gil, Y. Matias, and U. Vishkin. A fast parallel dictionary. In preparation, 1990."},{"key":"28_CR50","doi-asserted-by":"crossref","unstructured":"Y. Gil, F. Meyer auf der Heide, and A. Wigderson. Not all keys can be hashed in constant time. In Proc. of the 22nd Ann. ACM Symp. on Theory of Computing, pages 244\u2013253, 1990.","DOI":"10.1145\/100216.100247"},{"key":"28_CR51","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L.M. Goldschlager","year":"1982","unstructured":"L.M. Goldschlager. A universal interconnection pattern for parallel computers. J. Assoc. Comput. Mach., 29:1073\u20131086, 1982.","journal-title":"J. Assoc. Comput. Mach."},{"key":"28_CR52","doi-asserted-by":"crossref","unstructured":"A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. In Proceedings 19th Annual ACM Symposium on Theory of Computing, pages 315\u2013324, 1987.","DOI":"10.1145\/28395.28429"},{"key":"28_CR53","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/3-540-17179-7_28","volume":"241","author":"A. Gibbons","year":"1986","unstructured":"A. Gibbons and W. Rytter. An optimal parallel algorithm for dynamic evaluation and its applications. In Proceedings of the sixth Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science 241, pages 453\u2013469. Springer-Verlag, 1986.","journal-title":"Lecture Notes in Computer Science"},{"key":"28_CR54","volume-title":"Efficient Parallel Algorithms","author":"A. Gibbons","year":"1988","unstructured":"A. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press, Cambridge, 1988."},{"key":"28_CR55","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0890-5401(87)90062-9","volume":"75","author":"T. Hagerup","year":"1987","unstructured":"T. Hagerup. Towards optimal parallel bucket sorting. Information and Computation, 75:39\u201351, 1987.","journal-title":"Information and Computation"},{"key":"28_CR56","doi-asserted-by":"crossref","unstructured":"T. Hagerup. Constant-time parallel integer sorting. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, 1991.","DOI":"10.1145\/103418.103452"},{"key":"28_CR57","doi-asserted-by":"crossref","unstructured":"T. Hagerup. Fast parallel generation of random permutations. In Proc. of 18th ICALP, 1991.","DOI":"10.1007\/3-540-54233-7_151"},{"key":"28_CR58","doi-asserted-by":"crossref","unstructured":"T. Hagerup, M. Chrobak, and K. Diks. Parallel 5-coloring of planar graphs. In Proc. of 14th ICALP, pages 304\u2013313, 1987.","DOI":"10.1007\/3-540-18088-5_25"},{"issue":"8","key":"28_CR59","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/359138.359141","volume":"22","author":"D.S. Hirschberg","year":"1979","unstructured":"D.S. Hirschberg, A.K. Chandra, and D.V. Sarwate. Computing connected components on parallel computers. Comm. ACM, 22,8:461\u2013464, 1979.","journal-title":"Comm. ACM"},{"key":"28_CR60","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1145\/359576.359582","volume":"21","author":"D. S. Hirschberg","year":"1978","unstructured":"D. S. Hirschberg. Fast parallel sorting algorithms. Comm. ACM, 21:657\u2013661, 1978.","journal-title":"Comm. ACM"},{"issue":"2","key":"28_CR61","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R.E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338\u2013355, May 1984.","journal-title":"SIAM J. Comput."},{"key":"28_CR62","volume-title":"Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1991","unstructured":"J. J\u00e1J\u00e1. Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA, 1991."},{"key":"28_CR63","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju and A.L. Delcher. Optimal parallel evaluation of tree-structured computations by ranking. In Proc. of AWOC 88, Lecture Notes in Computer Science No. 319, pages 101\u2013110. Springer-Verlag, 1988.","DOI":"10.1007\/BFb0040378"},{"key":"28_CR64","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0021-9800(68)80083-3","volume":"4","author":"R.M. Karp","year":"1968","unstructured":"R.M. Karp and W.L. Miranker. Parallel minimax search for a maximum. J. of Combinatorial Theory, 4:19\u201334, 1968.","journal-title":"J. of Combinatorial Theory"},{"key":"28_CR65","doi-asserted-by":"crossref","unstructured":"Z.M. Kedem, K.V. Palem, and P.G. Spirakis. Efficient robust parallel computations. In Proc. of the 22nd Ann. ACM Symp. on Theory of Computing, pages 138\u2013148, 1990.","DOI":"10.1145\/100216.100231"},{"key":"28_CR66","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"R.M. Karp and M.O. Rabin. Efficient randomized pattern-matching algorithms. IBM J. of Research and Development, 31:249\u2013260, 1987.","journal-title":"IBM J. of Research and Development"},{"key":"28_CR67","unstructured":"R.M. Karp and V. Ramachandran. A survey of parallel algorithms for shared-memory machines. Technical Report UCB\/CSD 88\/408, Computer Science Division (EECS) U. C. Berkeley, 1988. also, in Handbook of Theoretical Computer Science, North-Holland, to appear."},{"key":"28_CR68","doi-asserted-by":"crossref","unstructured":"P. Klein and J.H. Reif. An efficient parallel algorithm for planarity. J. Comp. Sys. Sci., 37, 1988.","DOI":"10.1016\/0022-0000(88)90006-2"},{"key":"28_CR69","first-page":"333","volume":"317","author":"C.P. Kruskal","year":"1988","unstructured":"C.P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. In Proc. of 15th ICALP, Springer LNCS 317, pages 333\u2013346, 1988.","journal-title":"Proc. of 15th ICALP, Springer LNCS"},{"key":"28_CR70","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"C-32","author":"C.P. Kruskal","year":"1983","unstructured":"C.P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. on Comp, C-32:942\u2013946, 1983.","journal-title":"IEEE Trans. on Comp"},{"key":"28_CR71","doi-asserted-by":"crossref","unstructured":"S. Khuller and B. Schieber. Efficient parallel algorithms for testing connectivity and finding disjoint s\u2013t paths in graphs. In Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 288\u2013293, 1989.","DOI":"10.1109\/SFCS.1989.63492"},{"key":"28_CR72","doi-asserted-by":"crossref","unstructured":"A. Karlin and E. Upfal. Parallel hashing \u2014 an efficient implementation of shared memory. In Proc. of the 18th Ann. ACM Symp. on Theory of Computing, pages 160\u2013168, 1986.","DOI":"10.1145\/12130.12146"},{"key":"28_CR73","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R.E. Ladner","year":"1980","unstructured":"R.E. Ladner and M.J. Fischer. Parallel prefix computation. J. Assoc. Comput. Mach., 27:831\u2013838, 1980.","journal-title":"J. Assoc. Comput. Mach."},{"key":"28_CR74","doi-asserted-by":"crossref","unstructured":"L. Lovasz. Computing ears and branching in parallel. In Proc. of the 26th IEEE Annual Symp. on Foundation of Computer Science, pages 464\u2013467, 1985.","DOI":"10.1109\/SFCS.1985.16"},{"key":"28_CR75","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15:1036\u20131053, 1986.","journal-title":"SIAM J. Comput."},{"key":"28_CR76","doi-asserted-by":"crossref","unstructured":"G.L. Miller and J.H. Reif. Parallel tree contraction and its application. In Proc. of the 26th IEEE Annual Symp. on Foundation of Computer Science, pages 478\u2013489, 1985.","DOI":"10.1109\/SFCS.1985.43"},{"key":"28_CR77","unstructured":"G.L. Miller and V.L. Ramachandran. Efficient parallel ear decomposition and applications. unpublished manuscript, 1986."},{"key":"28_CR78","doi-asserted-by":"crossref","unstructured":"G.L. Miller and V.L. Ramachandran. A new graph triconnectivity algorithm and its parallization. In Proc. of the 19th Ann. ACM Symp. on Theory of Computing, pages 335\u2013344, 1987.","DOI":"10.1145\/28395.28431"},{"key":"28_CR79","unstructured":"P.D. MacKenzie and Q.F. Stout. Ultra-fast expected time parallel algorithms. In Proc. of the 2nd Second ACM-SIAM Symposium on Discrete Algorithms, pages 414\u2013424, 1991."},{"key":"28_CR80","doi-asserted-by":"crossref","unstructured":"C. Martel, R. Subramonian, and A. Park. Asynchronous PRAMs are (almost) as good as synchronous PRAMs. In Proc. of the 31st IEEE Annual Symp. on Foundation of Computer Science, pages 590\u2013599, 1990.","DOI":"10.1109\/FSCS.1990.89580"},{"key":"28_CR81","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","volume":"47","author":"Y. Maon","year":"1986","unstructured":"Y. Maon, B. Schieber, and U. Vishkin. Parallel ear-decomposition search (EDS) and st-numbering in graphs. Theoretical Computer Science, 47:277\u2013298, 1986.","journal-title":"Theoretical Computer Science"},{"key":"28_CR82","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Informatica, 21:339\u2013374, 1984.","journal-title":"Acta Informatica"},{"key":"28_CR83","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. On parallel hashing and integer sorting. In Proc. of 17th ICALP, Springer LNCS 443, pages 729\u2013743, 1990. Also, in UMIACS-TR-90-13, Inst. for Advanced Computer Studies, Univ. of Maryland, Aug. 1990 (revised), and J. Algorithms, to appear.","DOI":"10.1007\/BFb0032070"},{"key":"28_CR84","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. Converting high probability into nearly-constant time \u2014 with applications to parallel hashing. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, 1991.","DOI":"10.1145\/103418.103453"},{"key":"28_CR85","volume-title":"Parallel Complexity Theory","author":"I. Parberry","year":"1987","unstructured":"I. Parberry. Parallel Complexity Theory. Pitman, London, 1987."},{"key":"28_CR86","doi-asserted-by":"crossref","unstructured":"N. Pippenger. On simultaneous resource bounds. In Proc. of the 20th IEEE Annual Symp. on Foundation of Computer Science, pages 307\u2013311, 1979.","DOI":"10.1109\/SFCS.1979.29"},{"key":"28_CR87","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1109\/TC.1978.1675167","volume":"C-27","author":"F. P. Preparata","year":"1978","unstructured":"F. P. Preparata. New parallel sorting schemes. IEEE trans. Computer, C-27:669\u2013673, 1978.","journal-title":"IEEE trans. Computer"},{"key":"28_CR88","doi-asserted-by":"crossref","unstructured":"P. Ragde. The parallel simplicity of compaction and chaining. In Proc. of 17th ICALP, Springer LNCS 443, pages 744\u2013751, 1990.","DOI":"10.1007\/BFb0032071"},{"key":"28_CR89","doi-asserted-by":"crossref","unstructured":"R. Raman. The power of collision: Randomized parallel algorithms for chaining and integer sorting. Technical Report TR-336 (revised version, January 1991), Computer Science Dept., Univ. of Rochester, 1990.","DOI":"10.1007\/3-540-53487-3_42"},{"key":"28_CR90","unstructured":"R. Raman. Optimal sub-logarithmic time integer sorting on a CRCW PRAM (note). manuscript, 1991."},{"key":"28_CR91","doi-asserted-by":"crossref","unstructured":"A.G. Ranade. How to emulate shared memory. In Proc. of the 28th IEEE Annual Symp. on Foundation of Computer Science, pages 185\u2013194, 1987.","DOI":"10.1109\/SFCS.1987.32"},{"key":"28_CR92","doi-asserted-by":"crossref","unstructured":"R. Reischuk. A fast probabilistic parallel sorting algorithm. In Proc. of the 22nd IEEE Annual Symp. on Foundation of Computer Science, pages 212\u2013219, October 1981.","DOI":"10.1109\/SFCS.1981.6"},{"volume-title":"Synthesis of Parallel Algorithms","year":"1991","key":"28_CR93","unstructured":"J.H. Reif, editor. Synthesis of Parallel Algorithms. Morgan Kaufmann, San Mateo, California, 1991."},{"key":"28_CR94","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0218041","volume":"18","author":"S. Rajasekaran","year":"1989","unstructured":"S. Rajasekaran and J.H. Reif. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. Comput., 18:594\u2013607, 1989.","journal-title":"SIAM J. Comput."},{"key":"28_CR95","doi-asserted-by":"crossref","unstructured":"V.L. Ramachandran and J.H. Reif. An optimal parallel algorithm for graph planarity. In Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 282\u2013287, 1989.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"28_CR96","doi-asserted-by":"crossref","unstructured":"J.H. Reif and S. Sen. Polling: a new random sampling technique for computational geometry. In Proc. of the 21st Ann. ACM Symp. on Theory of Computing, pages 394\u2013404, 1989.","DOI":"10.1145\/73007.73045"},{"key":"28_CR97","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/7531.7532","volume":"34","author":"J.H. Reif","year":"1987","unstructured":"J.H. Reif and L.G. Valiant. A logarithmic time sort for linear size networks. J. Assoc. Comput. Mach., 34:60\u201376, 1987.","journal-title":"J. Assoc. Comput. Mach."},{"key":"28_CR98","doi-asserted-by":"crossref","unstructured":"V.L. Ramachandran and U. Vishkin. Efficient parallel triconnectivity in logarithmic parallel time. In Proc. of AWOC 88, Lecture Notes in Computer Science No. 319, pages 33\u201342. Springer-Verlag, 1988.","DOI":"10.1007\/BFb0040371"},{"issue":"4","key":"28_CR99","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"J. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. JACM, 27(4):701\u2013717, 1980.","journal-title":"JACM"},{"issue":"4","key":"28_CR100","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/357114.357116","volume":"2","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz. Ultracomputers. ACM Transactions on Programming Languages and Systems, 2(4):484\u2013521, 1980.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"28_CR101","unstructured":"B. Schieber. Design and analysis of some parallel algorithms. PhD thesis, Dept. of Computer Science, Tel Aviv Univ., 1987."},{"key":"28_CR102","unstructured":"S. Sen. Finding an approximate-median with high-probability in constant time. Manuscript, 1989."},{"key":"28_CR103","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin. Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms, 2:88\u2013102, 1981.","journal-title":"J. Algorithms"},{"key":"28_CR104","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. An O(logn) parallel connectivity algorithm. J. Algorithms, 3:57\u201367, 1982.","journal-title":"J. Algorithms"},{"key":"28_CR105","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0196-6774(82)90013-X","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin. An O(n 2logn) parallel Max-Flow algorithm. J. Algorithms, 3:128\u2013146, 1982.","journal-title":"J. Algorithms"},{"issue":"6","key":"28_CR106","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization. SIAM Journal on Computing, 17(6):1253\u20131262, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"28_CR107","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0166-218X(90)90084-P","volume":"29","author":"B. Schieber","year":"1990","unstructured":"B. Schieber and U. Vishkin. Finding all nearest neighbors for convex polygons in parallel: a new lower bounds technique and a matching algorithm. Discrete Applied Math, 29:97\u2013111, 1990.","journal-title":"Discrete Applied Math"},{"key":"28_CR108","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. Finding biconnected components and computing tree functions in logarithmic parallel time. SIAM J. Computing, 14:862\u2013874, 1985.","journal-title":"SIAM J. Computing"},{"key":"28_CR109","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L.G. Valiant","year":"1975","unstructured":"L.G. Valiant. Parallelism in comparison problems. SIAM J. Comput., 4:348\u2013355, 1975.","journal-title":"SIAM J. Comput."},{"issue":"8","key":"28_CR110","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"L.G. Valiant. A bridging model for parallel computation. Comm. ACM, 33,8:103\u2013111, 1990.","journal-title":"Comm. ACM"},{"key":"28_CR111","unstructured":"U. Vishkin. Synchronous parallel computation \u2014 a survey. Technical Report TR 71, Dept. of Computer Science, Courant Institute, New York University, 1983."},{"key":"28_CR112","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(84)90028-8","volume":"32","author":"U. Vishkin","year":"1984","unstructured":"U. Vishkin. A parallel-design distributed-implementation (PDDI) general purpose computer. Theoretical Computer Science, 32:157\u2013172, 1984.","journal-title":"Theoretical Computer Science"},{"key":"28_CR113","doi-asserted-by":"crossref","unstructured":"U. Vishkin. Randomized speed-ups in parallel computations. In Proc. of the 16th Ann. ACM Symp. on Theory of Computing, pages 230\u2013239, 1984.","DOI":"10.1145\/800057.808686"},{"key":"28_CR114","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0020-0190(85)90025-0","volume":"20","author":"U. Vishkin","year":"1985","unstructured":"U. Vishkin. On efficient parallel strong orientation. Information Processing Letters, 20:235\u2013240, 1985.","journal-title":"Information Processing Letters"},{"issue":"1\u20133","key":"28_CR115","first-page":"91","volume":"67","author":"U. Vishkin","year":"1985","unstructured":"U. Vishkin. Optimal parallel pattern matching in strings. Information and Computation, 67,1\u20133:91\u2013113, 1985.","journal-title":"Information and Computation"},{"key":"28_CR116","unstructured":"U. Vishkin. A parallel blocking flow algorithm for acyclic networks. Technical Report UMIACS-TR-90-11, University of Maryland Inst. for Advanced Computer Studies, 1990."},{"issue":"1","key":"28_CR117","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/0220002","volume":"20","author":"U. Vishkin","year":"1991","unstructured":"U. Vishkin. Deterministic sampling \u2014 a new technique for fast pattern matching. SIAM J. Comput, 20(1):22\u201340, February 1991.","journal-title":"SIAM J. Comput"},{"issue":"4","key":"28_CR118","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1145\/321906.321911","volume":"22","author":"S. Winograd","year":"1975","unstructured":"S. Winograd. On the evaluation of certain arithmetic expressions. J. Assoc. Comput. Mach., 22,4:477\u2013492, 1975.","journal-title":"J. Assoc. Comput. Mach."},{"key":"28_CR119","volume-title":"The Complexity of Parallel Computations","author":"J. C. Wyllie","year":"1979","unstructured":"J. C. Wyllie. The Complexity of Parallel Computations. PhD thesis, Computer Science Department, Conell University, Ithaca, NY, 1979."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_148.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:16:53Z","timestamp":1742591813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":119,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_148","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}