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 k 1 nodes of a set of linked lists. For the case k = 1, on two-dimensional meshes, the deterministic version takes 105 \Delta n steps; the randomized version 80 \Delta n steps. Extensions for larger k, require 31 \Delta k \Delta n and 10 \Delta k \Delta n, steps respectively. Keywords: parallel algorithms, interconnection networks, meshes, list ranking, ruling sets, randomization. 1 Introduction 1.1 General Notions Lists. A linked list, hereafter just list, is a basic data structure: it consists of nodes which are linked together, such that every node has precisely one predecessor and one successor, except for..