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

DOI10.3103/S0027132221010071zbMath1472.05065OpenAlexW3179321748MaRDI QIDQ1980441

G. V. Bokov, M. I. Shchekalev, Valerii B. Kudryavtsev

Publication date: 8 September 2021

Published in: Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s0027132221010071

zbMATH Keywords

complexityShannon functiontopological sortinglinear ordering of verticesweighted directed acyclic graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Cites Work

• Topological orderings of weighted directed acyclic graphs
• On the minimal packing of a tree with fixed vertices
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of a linear ordering of weighted directed acyclic graphs