Lower bounds for parallel computation on linked structures
Faith Ellen Fich, Vijaya Ramachandran · 1990
The time required to compute any function of a collection of circular doubly linked lists on a CROW PRAR4 is shown to be at most a constant factor more than on a CREW PRAM, but this is not true for singly linked lists.A tight lower bound of R(loglog* n) for colouring an n node doubly linked list on a CROW PRAM using a constant number of colours is also obtained.