ON THE POWER OF SOME PRAM MODELS

References

• S.G. Akl . An optimal algorithm Tor parallel selection. Information Processing Letters , 19 47 – 50 , 1984 .
   Web of Science ®Google Scholar
• S.G. Akl . Parallel Computation Models and Methods. Prentice-Hall , 1997 .
   Google Scholar
• S.G. Akl , L. Chen . Efficient parallel algorithms on proper circular arc graphs. IEICE Transactions on Information and Systems , E 79 -D( 8 ) 1015 – 1020 , 1996 .
   Google Scholar
• S.G. Akl , G.R. Guenther . Broadcasting with selective reduction. In G.X. Ritter (ed.) , Proceedings, 11th IF1P World Computer Congress , pp. 515 – 520 , North-Holland , 1989 .
   Google Scholar
• S.G. Akl and I. Stojmenovic . Broadcasting with selective reduction: A powerful model of parallel computation . In A.Y. Zomaya (ed) , Parallel and Distributed Computing Hand-book , pp. 192 – 222 . McGraw-Hill , New York , 1996 .
   Google Scholar
• P.W. Beame , J. Hastad . Optimal bounds for decision problems on the CRCW PRAM. Journal of the ACM , 36 ( 3 ) 643 – 670 , 1989 .
   Web of Science ®Google Scholar
• R.P. Brent . The parallel evaluation of general arithmetic expressions. Journal of the ACM , 21 201 – 208 , 1974 .
   Web of Science ®Google Scholar
• L. Chen . Optimal parallel time bounds for the maximum clique problem on intervals. Information Processing Utters , 42 ( 4 ) 197 – 201 , |y1992|.
   Web of Science ®Google Scholar
• L. Chen . Efficient parallel recognition of some circular arc graphs, II. Algorithmica , 17 ( 3 ) 266 – 280 , 1997 .
   Web of Science ®Google Scholar
• R. Cole . Parallel merge sort. SIAM Journal on Computing , 17 ( 4 ) 770 – 785 , 1988 . Correc-tion, ibid. 22(6) 1349, 1993 .
   Web of Science ®Google Scholar
• R. Cole and U. Vishkin . Faster optimal parallel prefix sums and list ranking . Information and Computation , 81 ( 3 ): 334 – 352 , 1989 .
   Web of Science ®Google Scholar
• D. Culler , R.M. Karp , D. Patterson , A. Sahay , K.E, Schauser, E. Santos , R. Subramonian , T. von Eicken . LogP towards a realistic model of parallel computation. In Proceedings, ACM Symposium on Principles and Practice of Parallel Programming , pp. 1 – 12 , 1993 .
   Google Scholar
• D. Eppstein , Z. Galil. Parallel algorithmic techniques for combinatorial computation. Ann. Rev. Comput. Sci. , 3 p233–283 p, 1988 .
   Web of Science ®Google Scholar
• F. Fich , F. Meyer auf der HeideA. Wigderson. Lower bounds for parallel random access machines with unbounded shared memory. In F. Preparata (ed.) , Advances in Com-puting Research , Vol. 4 , pp. 1 – 15 , JAI Press , 1987 .
   Google Scholar
• F.E. Fich , P.L. Ragde , A. Wigderson . Simulations among concurrent-write PRAMs. Algorithmica , 3 ( 1 ) 43 – 51 , 1988 .
   Web of Science ®Google Scholar
• R.M. Karp , V. Ramachandran . Parallel algorithms for shared-memory machines. In J. van Leeuwen (ed.) , Handbook of Theoretical Computer Science , Vol. A , pp. 869 – 941 , North Holland , Amsterdam , 1990 .
   Google Scholar
• R.E. Ladner and M.J. Fischer , Parallel prefix computation . Journal of the ACM , 27 ( 4 ) 831 – 838 , 1980 .
   Web of Science ®Google Scholar
• L.F. Lindon and S.G. Akl . An optimal implementation of broadcasting with selective reduction . IEEE Transactions on Parallel and Distributed Systems , 4 ( 3 ): 256 – 269 , 1993 .
   Web of Science ®Google Scholar
• Y. Shiloach , U. Vishkin . Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms , 2 88 – 102 , 1981 .
   Web of Science ®Google Scholar
• L. Valiant . A bridging model for parallel computation. Communications of the ACM , 33 ( 8 ) 103 – 111 . 1990 .
   Web of Science ®Google Scholar
• J. Wiedermann . Quo vadetis, parallel machine models? In J. van Leeuwen (ed.). Computer Science Today Recent Trends and Developments, Lecture Notes in Computer Science , Vol. 1000 , pp. 101 – 114 . Springer-Verlag , 1995 .
   Google Scholar