On Parallel Searching

DOI10.1137/0214051zbMath0607.68047OpenAlexW2018729969MaRDI QIDQ3746899

Marc Snir

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3a5858e8517f28fa586364daffb34160c437bf78

zbMATH Keywords

parallel algorithmsparallel computationscomparison-based algorithmscomplexity of searching a sorted table

Mathematics Subject Classification ID

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

Related Items (28)

A fast algorithm for scalar Nevanlinna-Pick interpolation ⋮ Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ Routing, merging, and sorting on parallel models of computation ⋮ Fast integer merging on the EREW PRAM ⋮ An insight on PRAM computational bounds ⋮ Retrieval of scattered information by EREW, CREW and CRCW PRAMs ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ Limits on the power of concurrent-write parallel machines ⋮ Polynomial terse sets ⋮ Retrieval of scattered information by EREW, CREW, and CRCW PRAMs ⋮ Optimal cooperative search in fractional cascaded data structures ⋮ The complexity of parallel prefix problems on small domains ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ On separating the EREW and CREW PRAM models ⋮ Fast integer merging on the EREW PRAM ⋮ A complexity theory of efficient parallel algorithms ⋮ Pipelined search on coarse grained networks ⋮ Incomparability in parallel computation ⋮ Heaps with bits ⋮ PRAMs with variable word-size ⋮ Optimal merging and sorting on the EREW PRAM ⋮ Parallel algorithms for nevanlinna-pick interpolation:the scalar case^∗ ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ Parallel random access machines with bounded memory wordsize ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Restricted CRCW PRAMs ⋮ Improving the efficiency of parallel minimum spanning tree algorithms ⋮ Space-efficient parallel merging

This page was built for publication: On Parallel Searching