A unidirectional ring partition problem
Jyun‐Jy Hu, Shi-Nine Yang, Maw‐Sheng Chern · Networks · 1993
Abstract 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 communication 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 that C(P*) = minpC(P). In this paper, we first formulate the ring partition problem into a recurrence relation. By solving the recurrence relation, we show that the ring partition can be accomplished distributively in one pass, i.e., the message complexity of our distributed ring partition algorithm is O(|V|), which is optimal. © 1993 by John Wiley & Sons, Inc.