Space-efficient parallel merging

J. Katajainen; C. Levcopoulos; O. Petersson

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 4, page 295-310
  • ISSN: 0988-3754

How to cite

top

Katajainen, J., Levcopoulos, C., and Petersson, O.. "Space-efficient parallel merging." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 27.4 (1993): 295-310. <http://eudml.org/doc/92452>.

@article{Katajainen1993,
author = {Katajainen, J., Levcopoulos, C., Petersson, O.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {parallel merging; EREW PRAM; Direct Connection Machine; CREW PRAM},
language = {eng},
number = {4},
pages = {295-310},
publisher = {EDP-Sciences},
title = {Space-efficient parallel merging},
url = {http://eudml.org/doc/92452},
volume = {27},
year = {1993},
}

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
PB - EDP-Sciences
VL - 27
IS - 4
SP - 295
EP - 310
LA - eng
KW - parallel merging; EREW PRAM; Direct Connection Machine; CREW PRAM
UR - http://eudml.org/doc/92452
ER -

References

top
  1. 1. S. G. AKL, The Design and Analysis of Parallel Algorithms, Prentice-Hall, Englewood Cliffs, N.J., 1989. Zbl0754.68053
  2. 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. Zbl0677.90054MR1016684
  3. 3. K. E. BATCHER, Sorting networks and their applications, Proc. of AFIPS Spring Joint Computer Conf., 1968, pp. 307-314. 
  4. 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. Zbl0677.68070MR986662
  5. 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. Zbl0603.68065MR788835
  6. 6. R. COLE, Parallel merge sort, SIAM J. Comput., 17, 1988, pp. 770-785. Zbl0651.68077MR953293
  7. 7. E. DEKEL and I. OZSVATH, Parallel external merging, J. Parallel Distr. Comput., 6, 1989, pp. 623-635. 
  8. 8. D. EPPSTEIN and Z. GALIL, Parallel algorithmic techniques for combinatorial computation, Annual Reviews in Computer Science, 3, 1988, pp. 233-283. Zbl0691.68037MR1001205
  9. 9. X. GUAN and M. A. LANGSTON, Time-space optimal parallel merging and sorting, IEEE Trans. Comput., 40, 1991, pp. 596-602. MR1110897
  10. 10. T. HAGERUP and C. RÜB, Optimal merging and sorting on the EREW PRAM, Inform. Process. Lett., 33, 1989, pp. 181-185. Zbl0689.68085MR1049685
  11. 11. B.-C. HUANG and M. A. LANGSTON, Practical in-place merging, Comm. ACM, 31, 1988, pp. 348-352. 
  12. 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. 13. J. JÁJÁ, An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992. Zbl0781.68009
  14. 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. Zbl0900.68267MR1127183
  15. 15. M. A. KRONROD, An optimal ordering algorithm without a field of operation, Dokladi Akademia Nauk SSSR, 186, 1969, pp. 1256-1258. Zbl0236.68017MR246793
  16. 16. C. P. KRUSKAL, Searching, merging, and sorting in parallel computation, IEEE Trans. Comput., C-32, 1983, pp. 942-946. Zbl0525.68039MR761981
  17. 17. C. P. KRUSKAL, L. RUDOLPH and M. SNIR, A complexity theory of efficient parallel algorithms, Theoret. Comput. Sci., 71, 1990, pp. 95-132. Zbl0699.68069MR1050080
  18. 18. H. MANNILA and E. UKKONEN, A simple linear-time algorithm for in situ merging, Inform. Process. Lett., 18, 1984, pp. 203-208. MR757978
  19. 19. F. P. PREPARATA, New parallel-sorting schemes, IEEE Trans. Comput., C-27, 1978, pp. 669-673. Zbl0379.68025MR495166
  20. 20. M. J. QUINN, Designing Efficient Algorithms for Parallel Computers, North-Holland, New York, 1987. Zbl0634.68020
  21. 21. J. SALOWE and W. STEIGER, Simplified stable merging tasks, J. Algorithms, 8, 1987, pp. 557-571. Zbl0641.68092MR920507
  22. 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. Zbl0707.68040MR1078306
  23. 23. J. T. SCHWARTZ, Ultracomputers, ACM Trans. Program. Lang. Syst., 2, 1980, pp. 484-521. Zbl0468.68027
  24. 24. Y. SHILOACH and U. VISHKIN, Finding the maximum, merging, and sorting in a parallel computational model, J. Algorithms, 12, 1981, pp. 88-102. Zbl0456.68062MR640514
  25. 25. M. SNIR, On parallel searching, SIAM J. Comput., 15, 1985, pp. 688-708. Zbl0607.68047MR795940
  26. 26. H. S. STONE, Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, 1971, pp. 153-161. Zbl0214.42703
  27. 27. L. G. VALIANT, General purpose parallel architectures In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. North-Holland, Amsterdam, The Netherlands, 1990. Zbl0900.68257MR1127184

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.