A UNIDIRECTIONAL RING PARTITION PROBLEM

Let R = (V, E) be a unidirectional ring network where V corresponds to the set of nodes and E corresponds to the set of directed communicati on links. A partition of R divides R into several disjoint chains. For each partition P, there is associated a communication cost C(P). The optimal ring partition problem is to find a partition P of R such tha t C(P) = min(p)C(P). In this paper, we first formulate the ring parti tion problem into a recurrence relation. By solving the recurrence rel ation, we show that the ring partition can be accomplished distributiv ely in one pass, i.e., the message complexity of our distributed ring partition algorithm is O(Absolute value of V), which is optimal.