Ranking the vertices of an r-partite paired comparison digraph

AbstractA paired comparison digraph D is a weighted digraph in which the sum of the weights of arcs, if any, joining two vertices is exactly one. A one-to-one mapping from V(D) onto {1,2…,|V(D)|} is called a ranking of D, and a ranking α of D is optimal if the backward length of α is minimum. We say that D is r-partite if V(D) can be partitioned into V1∪…∪Vr so that every arc of D joins a vertex of Vi to a vertex of Vi, where i ≠ j. We show that we can easily obtain all the optimal rankings of a certain r-partite paired comparison digraph