Pointer Jumping

Pointer jumping, also called path doubling, is a design technique for parallel algorithms that operate on pointer-based structures such as linked lists and directed graphs. At each step, every node replaces its pointer to its immediate successor with a pointer to that successor's own successor, so the distance a pointer reaches doubles on each round, letting a path of length n be traversed in time proportional to the logarithm of n rather than to n itself. According to the computer scientist Joseph JaJa, the earliest uses of the idea appeared in early parallel graph algorithms and list-ranking problems, and by the 1990s the term pointer jumping was standard in parallel-algorithms textbooks; applications include list ranking, finding roots of forests, computing connected components, minimum spanning trees and biconnected components, as well as uses outside graph theory in computer vision, image compression and Bayesian inference.