On the Complexity of a Linear Ordering of Weighted Directed Acyclic Graphs

被引：0

作者：

Shchekalev, M. I. ^{[1
]}

Bokov, G. V. ^{[1
]}

Kudryavtsev, V. B. ^{[1
]}

机构：

[1] Lomonosov Moscow State Univ, Fac Mech & Math, Chair Math Theory Intelligent Syst, Moscow 119992, Russia

来源：

MOSCOW UNIVERSITY MATHEMATICS BULLETIN | 2021年 / 76卷 / 01期

关键词：

weighted directed acyclic graphs; linear ordering of vertices; topological sorting; complexity; Shannon function;

D O I：

10.3103/S0027132221010071

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider weighted directed acyclic graphs to whose edges nonnegative integers as weights are assigned. The complexity of a linear ordering of vertices is examined for these graphs in the order of topological sorting. An accurate estimate for the Shannon function of the complexity of the linear ordering problem for weighted directed acyclic graphs is obtained.

引用

页码：35 / 36

页数：2