×

Ranking the vertices of a complete multipartite paired comparison digraph. (English) Zbl 0868.68083

Summary: A paired comparison digraph (abbreviated to PCD) \(D=(V,A)\) is a weighted digraph in which the sum of the weights of arcs, if any, joining two distinct vertices equals one. A one-to-one mapping \(\alpha\) from \(V\) onto \(\{1,2,\dots,|V|\}\) is called a ranking of \(D\). For every ranking \(\alpha\), an arc \(vu\in A\) is said to be forward if \(\alpha(v)< \alpha(u)\), and backward otherwise. The length of an arc \(vu\) is \(\ell(vu)=\varepsilon(vu)|\alpha(v)-\alpha(u)|\), where \(\varepsilon(vu)\) is the weight of \(vu\). The forward (backward) length \(f_D(\alpha) (b_D(\alpha))\) of \(\alpha\) is the sum of the lengths of all forward (backward) arcs of \(D\). A ranking \(\alpha\) is forward (backward) optimal if \(f(\alpha)\) is maximum (\(b(\alpha)\) is minimum). M. Kano [Discrete Appl. Math. 17, 245-253 (1987; Zbl 0617.05031)] characterized all backward optimal rankings of a complete multipartite PCD \(L\) and raised the problem to characterize all forward optimal rankings of a complete multipartite PCD \(L\). We show how to transform the last problem into the single machine job sequencing problem of minimizing total weighted completion time subject to precedence “parallel chains” constraints. This provides an algorithm for generating all forward optimal rankings of \(L\) as well as a polynomial algorithm for finding the average rank of every vertex in \(L\) over all forward optimal rankings of \(L\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0617.05031

Software:

heapsort
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Brightwell, G.; Winkler, P., Counting linear extensions, Order, 8, 225-242 (1991) · Zbl 0759.06001
[2] Garey, M. R.; Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[3] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[4] Gutin, G., Determining the ranks of vertices in a complete multipartite graph of paired comparisons, Automat. Remote Control, 10, 139-147 (1989)
[5] Horn, W. A., Single machine job sequencing with treelike precedence ordering and linear delay penalties, SIAM J. Appl. Math., 23, 189-202 (1972) · Zbl 0224.90025
[6] Kano, M., Ranking the vertices of an \(r\)-partite paired comparison digraph, Discrete Appl. Math., 17, 245-253 (1987) · Zbl 0617.05031
[7] Kano, M.; Sakamoto, A., Ranking the vertices of a weighted digraph using the length of forward arcs, Networks, 13, 143-151 (1983) · Zbl 0507.05035
[8] Kano, M.; Sakamoto, A., Ranking the vertices of a paired comparison digraph with normal completeness theorems, Bull. Fac. Engrg. Tokushima Univ., 20, 119-128 (1983)
[9] Kano, M.; Sakamoto, A., Ranking the vertices of a paired comparison digraph, SIAM J. Algebraic Discrete Methods, 6, 2-79 (1985) · Zbl 0572.05030
[10] Sidney, J. B., Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, Oper. Res., 23, 283-298 (1975) · Zbl 0304.90058
[11] Williams, J. W.J., Algorithm 232: Heapsort, Comm. ACM, 7, 347-348 (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.