Space-efficient parallel merging

DOI10.1051/ITA/1993270402951MaRDI QIDQ3142264zbMATH OpenOpenAlexFDO

Authors Jyrki Katajainen, Ola Petersson, Christos Levcopoulos

Publication date 15 November 1993

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92452

zbMATH Keywords

CREW PRAMEREW PRAMparallel mergingDirect Connection Machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Distributed algorithms (68W15)

Recommendations

• On parallel integer merging
• Optimal parallel merging and sorting algorithms using \(\sqrt{N}\) processors without memory contention
• Fast integer merging on the EREW PRAM
• Fast integer merging on the EREW PRAM
• Optimal merging and sorting on the EREW PRAM

Cites work

• scientific article; zbMATH DE number 4131653 (Why is no real title available?)
• scientific article; zbMATH DE number 4033059 (Why is no real title available?)
• scientific article; zbMATH DE number 53193 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 1142307 (Why is no real title available?)
• scientific article; zbMATH DE number 3374945 (Why is no real title available?)
• A complexity theory of efficient parallel algorithms
• Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
• Finding the maximum, merging, and sorting in a parallel computation model
• New Parallel-Sorting Schemes
• On Parallel Searching
• Optimal merging and sorting on the EREW PRAM
• Parallel Merge Sort
• Parallel Processing with the Perfect Shuffle
• Parallel approximation algorithms for bin packing
• Routing, merging, and sorting on parallel models of computation
• Searching, Merging, and Sorting in Parallel Computation
• Simplified stable merging tasks
• Time-space optimal parallel merging and sorting
• Ultracomputers

Cited in

(17)

• Parallel algorithms for merging and sorting
• Simplified stable merging tasks
• Parallel Merge Sort
• Merging and sorting strings in parallel
• scientific article; zbMATH DE number 3949727 (Why is no real title available?)
• Optimal merging and sorting on the EREW PRAM
• On saving space in parallel computation
• ON COST-OPTIMAL MERGE OF TWO INTRANSITIVE SORTED SEQUENCES
• Sorting multisets stably in minimum space
• Optimal parallel string algorithms: sorting, merging and computing the minimum
• On parallel integer merging
• Direct merging of delta encoded files
• Parallel merge sort using comparison matrices. II
• Perfectly load-balanced, stable, synchronization-free parallel merge
• Merging on the BSP model
• Sorting multisets stably in minimum space
• scientific article; zbMATH DE number 6117286 (Why is no real title available?)

This page was built for publication: Space-efficient parallel merging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3142264)