@article{ITA_1993__27_4_295_0, author = {Katajainen, J. and Levcopoulos, C. and Petersson, O.}, title = {Space-efficient parallel merging}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {295--310}, publisher = {EDP-Sciences}, volume = {27}, number = {4}, year = {1993}, mrnumber = {1238052}, zbl = {0778.68037}, language = {en}, url = {http://www.numdam.org/item/ITA_1993__27_4_295_0/} }
TY - JOUR AU - Katajainen, J. AU - Levcopoulos, C. AU - Petersson, O. TI - Space-efficient parallel merging JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1993 SP - 295 EP - 310 VL - 27 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1993__27_4_295_0/ LA - en ID - ITA_1993__27_4_295_0 ER -
%0 Journal Article %A Katajainen, J. %A Levcopoulos, C. %A Petersson, O. %T Space-efficient parallel merging %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1993 %P 295-310 %V 27 %N 4 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1993__27_4_295_0/ %G en %F ITA_1993__27_4_295_0
Katajainen, J.; Levcopoulos, C.; Petersson, O. Space-efficient parallel merging. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 4, pp. 295-310. http://www.numdam.org/item/ITA_1993__27_4_295_0/
1. The Design and Analysis of Parallel Algorithms, Prentice-Hall, Englewood Cliffs, N.J., 1989. | Zbl
,2. Parallel approximation algorithms for bin packing, Inform. and Comput., 82, 1989, pp. 262-277. | MR | Zbl
, and ,3. Sorting networks and their applications, Proc. of AFIPS Spring Joint Computer Conf., 1968, pp. 307-314.
,4. Adaptive bitonic sorting: An optimal parallel algorithm for shared memory models, SIAM J. Comput., 18, 1989, pp. 216-228. | MR | Zbl
and ,5. Routing, sorting, and merging on parallel models of computation, J. Comput. System Sci., 30, 1985, pp. 130-145. | MR | Zbl
and ,6. Parallel merge sort, SIAM J. Comput., 17, 1988, pp. 770-785. | MR | Zbl
,7. Parallel external merging, J. Parallel Distr. Comput., 6, 1989, pp. 623-635.
and ,8. Parallel algorithmic techniques for combinatorial computation, Annual Reviews in Computer Science, 3, 1988, pp. 233-283. | MR
and ,9. Time-space optimal parallel merging and sorting, IEEE Trans. Comput., 40, 1991, pp. 596-602. | MR
and ,10. Optimal merging and sorting on the EREW PRAM, Inform. Process. Lett., 33, 1989, pp. 181-185. | MR | Zbl
and ,11. Practical in-place merging, Comm. ACM, 31, 1988, pp. 348-352.
and ,12. Fast stable merging and sorting in constant extra space, Proc. Internat. Conf. on Computing and Information, 1989, pp. 71-80.
and ,13. An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992. | Zbl
,14. A survey of parallel algorithms for shared memory machines, In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. North-Holland, Amsterdam, The Netherlands, 1990. | MR | Zbl
and ,15. An optimal ordering algorithm without a field of operation, Dokladi Akademia Nauk SSSR, 186, 1969, pp. 1256-1258. | MR | Zbl
,16. Searching, merging, and sorting in parallel computation, IEEE Trans. Comput., C-32, 1983, pp. 942-946. | MR | Zbl
,17. A complexity theory of efficient parallel algorithms, Theoret. Comput. Sci., 71, 1990, pp. 95-132. | MR | Zbl
, and ,18. A simple linear-time algorithm for in situ merging, Inform. Process. Lett., 18, 1984, pp. 203-208. | MR
and ,19. New parallel-sorting schemes, IEEE Trans. Comput., C-27, 1978, pp. 669-673. | MR | Zbl
,20. Designing Efficient Algorithms for Parallel Computers, North-Holland, New York, 1987. | Zbl
,21. Simplified stable merging tasks, J. Algorithms, 8, 1987, pp. 557-571. | MR | Zbl
and ,22. Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm, Discrete Applied Math., 29, 1990 pp. 97-111. | MR | Zbl
and ,23. Ultracomputers, ACM Trans. Program. Lang. Syst., 2, 1980, pp. 484-521. | Zbl
,24. Finding the maximum, merging, and sorting in a parallel computational model, J. Algorithms, 12, 1981, pp. 88-102. | MR | Zbl
and ,25. On parallel searching, SIAM J. Comput., 15, 1985, pp. 688-708. | MR | Zbl
,26. Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, 1971, pp. 153-161. | Zbl
,27. General purpose parallel architectures In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. North-Holland, Amsterdam, The Netherlands, 1990. | MR | Zbl
,