Abstract.
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 \geq 1\) nodes of a set of linked lists. For the case \(k = 1\), on two-dimensional meshes, the deterministic version takes \(105 \cdot n\) steps; the randomized version \(80 \cdot n\) steps. Extensions for larger \(k\), require \(31 \cdot k \cdot n\) and \(10 \cdot k \cdot n\), steps respectively.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: 24 November 1995 / 24 October 1997
Rights and permissions
About this article
Cite this article
Sibeyn, J. List ranking on meshes. Acta Informatica 35, 543–566 (1998). https://doi.org/10.1007/s002360050131
Issue Date:
DOI: https://doi.org/10.1007/s002360050131