List ranking on meshes

The list-ranking problem is considered for parallel computers which communicate through an interconnection network. The algorithms are based on the idea of repeatedly removing the complement of a ruling set. By specific refinements and detailed analysis, earlier results are improved considerably. We concentrate on meshes, but most of the ideas are more general. Each PU holds nodes of a set of linked lists. For the case , on two-dimensional meshes, the deterministic version takes steps; the randomized version steps. Extensions for larger , require and , steps respectively. Received: 24 November 1995 / 24 October 1997