Ranking the vertices of a weighted digraph using the length of forward arcs
Mikio Kanō, Akio Sakamoto · Networks · 1983
Abstract Let D = (V, A ) be a weighted digraph with vertex set V and arc set A , and let α be a one‐to‐one mapping from V onto the set of integers {1, 2, …, | V |}. A mapping α is called a ranking of D . According to a ranking α, the arc set A is naturally partitioned into the set of forward arcs of α and that of backward ones. By using these subsets of rankings, we define three kinds of optimal rankings: forward optimal rankings, backward optimal rankings, and mutual optimal rankings. Since many results on the backward optimal rankings are already known, we mainly discuss the properties of the forward optimal rankings and the mutual ones in the present article.