Résumé: 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 k > 1 nodes of a set of linked lists. For the case k =1, on two-dimensional meshes, the deterministic version takes 105.n steps; the randomized version 80.n steps. Extensions for larger k, require 31 k . n and 10 . k . n, steps respectively.

Langue: Anglais