Geodesic
On the complexity of a linear ordering of weighted directed acyclic graphs
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2021), pp. 55-57 
M. I. Shekalev; G. V. Bokov; V. B. Kudryavtsev. On the complexity of a linear ordering of weighted directed acyclic graphs. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2021), pp. 55-57. http://geodesic.mathdoc.fr/item/VMUMM_2021_1_a8/
@article{VMUMM_2021_1_a8,
     author = {M. I. Shekalev and G. V. Bokov and V. B. Kudryavtsev},
     title = {On the complexity of a linear ordering of weighted directed acyclic graphs},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {55--57},
     year = {2021},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2021_1_a8/}
}
TY  - JOUR
AU  - M. I. Shekalev
AU  - G. V. Bokov
AU  - V. B. Kudryavtsev
TI  - On the complexity of a linear ordering of weighted directed acyclic graphs
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2021
SP  - 55
EP  - 57
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2021_1_a8/
LA  - ru
ID  - VMUMM_2021_1_a8
ER  - 
%0 Journal Article
%A M. I. Shekalev
%A G. V. Bokov
%A V. B. Kudryavtsev
%T On the complexity of a linear ordering of weighted directed acyclic graphs
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2021
%P 55-57
%N 1
%U http://geodesic.mathdoc.fr/item/VMUMM_2021_1_a8/
%G ru
%F VMUMM_2021_1_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is focused on weighted directed acyclic graphs with edges weighted with nonnegative integers. The complexity of linear ordering of vertices is considered for these graphs with respect to topological sorting. An accurate estimate of the Shannon function for the complexity of linear ordering of vertices for weighted directed acyclic graphs is obtained.

[1] Akho A.V., Lam M.S., Seti R., Ulman D.D., Kompilyatory: printsipy, tekhnologii i instrumentarii, 2-e izd., Vilyams, M., 2008

[2] Kormen T., Leizerson Ch., Rivest R., Shtain K., Algoritmy: postroenie i analiz, 2-e izd., Vilyams, M., 2005

[3] Egorov E.E., “O minimalnoi ukladke dereva s zakreplennymi vershinami”, Diskretn. matem., 9:1 (1997), 147–152

[4] Gerbner D., Keszegh B., Palmer C., Pálvölgyi D., “Topological orderings of weighted directed acyclic graphs”, Inform. Process. Lett., 116:9 (2016), 564–568

[5] Sedgewick R., Wayne K., Algorithms, 4th ed., Addison-Wesley Professional, B., 2011