Author name cluster

M. Dietzfelbinger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

1 paper

1 author row

I&C Journal 1993 Journal Article

An Optimal Parallel Dictionary

M. Dietzfelbinger
F.M. Aufderheide

A parallel dictionary is implemented on a randomized CRCW PRAM with p processors in such a way that n instructions (Insert, Delete, Lookup), n/p read in by each processor, can be executed in optimal expected time O(n/p). Further, the response time of each lookup is worst case constant. The construction is inspired by the sequential dynamic hashing strategy due to Dietzfelbinger et al. (in "Proceedings, 29th IEEE Symposium on Foundations of Computer Science, " pp. 524-531), which in turn is based on the perfect hashing scheme due to Fredman et al. (1984, J. Assoc. Comput. Mach. 31, 538-544).

Details DOI