Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with CREW:
TR97-008 | 16th March 1997
Noam Nisan, Ziv Bar-Yossef

Pointer Jumping Requires Concurrent Read

We consider the well known problem of determining the k'th
vertex reached by chasing pointers in a directed graph of
out-degree 1. The famous "pointer doubling" technique
provides an O(log k) parallel time algorithm on a
Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ... more >>>

ISSN 1433-8092 | Imprint