On the complexity of a linear ordering of weighted directed acyclic graphs
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2021), pp. 55-57
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.
@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},
publisher = {mathdoc},
number = {1},
year = {2021},
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 PB - mathdoc 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 %I mathdoc %U http://geodesic.mathdoc.fr/item/VMUMM_2021_1_a8/ %G ru %F VMUMM_2021_1_a8
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/