Space-efficient parallel merging

Katajainen, J.; Levcopoulos, C.; Petersson, O.

Katajainen, J. ; Levcopoulos, C. ; Petersson, O.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 4, pp. 295-310.

MR Zbl

@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://archive.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://archive.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://archive.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://archive.numdam.org/item/ITA_1993__27_4_295_0/

Bibliographie
Cité par

1. S. G. Akl, The Design and Analysis of Parallel Algorithms, Prentice-Hall, Englewood Cliffs, N.J., 1989. | Zbl

2. R. J. Anderson, E. W. Mayr and M. K. Warmuth, Parallel approximation algorithms for bin packing, Inform. and Comput., 82, 1989, pp. 262-277. | MR | Zbl

3. K. E. Batcher, Sorting networks and their applications, Proc. of AFIPS Spring Joint Computer Conf., 1968, pp. 307-314.

4. G. Bilardi and A. Nicolau, Adaptive bitonic sorting: An optimal parallel algorithm for shared memory models, SIAM J. Comput., 18, 1989, pp. 216-228. | MR | Zbl

5. A. Borodin and J. E. Hopcroft, Routing, sorting, and merging on parallel models of computation, J. Comput. System Sci., 30, 1985, pp. 130-145. | MR | Zbl

6. R. Cole, Parallel merge sort, SIAM J. Comput., 17, 1988, pp. 770-785. | MR | Zbl

7. E. Dekel and I. Ozsvath, Parallel external merging, J. Parallel Distr. Comput., 6, 1989, pp. 623-635.

8. D. Eppstein and Z. Galil, Parallel algorithmic techniques for combinatorial computation, Annual Reviews in Computer Science, 3, 1988, pp. 233-283. | MR

9. X. Guan and M. A. Langston, Time-space optimal parallel merging and sorting, IEEE Trans. Comput., 40, 1991, pp. 596-602. | MR

10. T. Hagerup and C. Rüb, Optimal merging and sorting on the EREW PRAM, Inform. Process. Lett., 33, 1989, pp. 181-185. | MR | Zbl

11. B.-C. Huang and M. A. Langston, Practical in-place merging, Comm. ACM, 31, 1988, pp. 348-352.

12. B.-C. Huang and M. A. Langston, Fast stable merging and sorting in constant extra space, Proc. Internat. Conf. on Computing and Information, 1989, pp. 71-80.

13. J. Jájá, An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992. | Zbl

14. R. M. Karp and V. Ramachandran, 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

15. M. A. Kronrod, An optimal ordering algorithm without a field of operation, Dokladi Akademia Nauk SSSR, 186, 1969, pp. 1256-1258. | MR | Zbl

16. C. P. Kruskal, Searching, merging, and sorting in parallel computation, IEEE Trans. Comput., C-32, 1983, pp. 942-946. | MR | Zbl

17. C. P. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms, Theoret. Comput. Sci., 71, 1990, pp. 95-132. | MR | Zbl

18. H. Mannila and E. Ukkonen, A simple linear-time algorithm for in situ merging, Inform. Process. Lett., 18, 1984, pp. 203-208. | MR

19. F. P. Preparata, New parallel-sorting schemes, IEEE Trans. Comput., C-27, 1978, pp. 669-673. | MR | Zbl

20. M. J. Quinn, Designing Efficient Algorithms for Parallel Computers, North-Holland, New York, 1987. | Zbl

21. J. Salowe and W. Steiger, Simplified stable merging tasks, J. Algorithms, 8, 1987, pp. 557-571. | MR | Zbl

22. B. Schieber and U. Vishkin, 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

23. J. T. Schwartz, Ultracomputers, ACM Trans. Program. Lang. Syst., 2, 1980, pp. 484-521. | Zbl

24. Y. Shiloach and U. Vishkin, Finding the maximum, merging, and sorting in a parallel computational model, J. Algorithms, 12, 1981, pp. 88-102. | MR | Zbl

25. M. Snir, On parallel searching, SIAM J. Comput., 15, 1985, pp. 688-708. | MR | Zbl

26. H. S. Stone, Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, 1971, pp. 153-161. | Zbl

27. L. G. Valiant, General purpose parallel architectures In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. North-Holland, Amsterdam, The Netherlands, 1990. | MR | Zbl