Space-efficient parallel merging
Katajainen, J. ; Levcopoulos, C. ; Petersson, O.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993), p. 295-310 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1993-01-01
@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},
     volume = {27},
     year = {1993},
     pages = {295-310},
     mrnumber = {1238052},
     zbl = {0778.68037},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 295-310. http://gdmltest.u-ga.fr/item/ITA_1993__27_4_295_0/

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

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 1016684 | Zbl 0677.90054

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 986662 | Zbl 0677.68070

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 788835 | Zbl 0603.68065

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

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 1001205

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

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

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 0781.68009

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 1127183 | Zbl 0900.68267

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

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

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 1050080 | Zbl 0699.68069

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

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

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

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

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 1078306 | Zbl 0707.68040

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

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 640514 | Zbl 0456.68062

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

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

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 1127184 | Zbl 0900.68257