Premium
A unidirectional ring partition problem
Author(s) -
Hu JyunJy,
Yang ShiNine,
Chern MawSheng
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230412
Subject(s) - partition (number theory) , disjoint sets , partition problem , combinatorics , mathematics , ring (chemistry) , discrete mathematics , chemistry , organic chemistry
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 *) = min p C(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.