On the complexity of a linear ordering of weighted directed acyclic graphs

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.