Ranking the Vertices of a Paired Comparison Digraph
Mikio Kanō, Akio Sakamoto · SIAM Journal on Algebraic and Discrete Methods · 1985
A paired comparison digraph $D = ( V,A )$ is a weighted digraph in which the sum of the weights of arcs, if any, joining two distinct vertices is exactly one; otherwise, there exist no arcs joining them. A one-to-one mapping $\alpha$ from V onto $\{ 1,2, \cdots , | V | \}$ is called a ranking of D. We define the backward arcs and the backward length of $\alpha$. An optimal ranking of D is a ranking whose backward length is minimum among those of all rankings of D. Our method of ranking the vertices of D is one that makes use of these optimal rankings. For certain classes of paired comparison digraphs, we show that the optimal rankings can be explicitly computed.