@techreport{Sibeyn97,
TITLE = {From parallel to external list ranking},
AUTHOR = {Sibeyn, Jop},
LANGUAGE = {eng},
NUMBER = {MPI-I-1997-1-021},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1997},
DATE = {1997},
ABSTRACT = {Novel algorithms are presented for parallel and external memory list-ranking. The same algorithms can be used for computing basic tree functions, such as the depth of a node. The parallel algorithm stands out through its low memory use, its simplicity and its performance. For a large range of problem sizes, it is almost as fast as the fastest previous algorithms. On a Paragon with 100 PUs, each holding 10^6 nodes, we obtain speed-up 25. For external-memory list-ranking, the best algorithm so far is an optimized version of independent-set-removal. Actually, this algorithm is not good at all: for a list of length N, the paging volume is about 72 N. Our new algorithm reduces this to 18 N. The algorithm has been implemented, and the theoretical results are confirmed.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}