Premium
Ranking the vertices of a weighted digraph using the length of forward arcs
Author(s) -
Kano Mikio,
Sakamoto Akio
Publication year - 1983
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.3230130109
Subject(s) - digraph , ranking (information retrieval) , mathematics , combinatorics , vertex (graph theory) , set (abstract data type) , arc (geometry) , discrete mathematics , computer science , graph , artificial intelligence , geometry , programming language
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.