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

DOI10.3103/S0027132221010071MaRDI QIDQ1980441zbMATH OpenOpenAlexFDO

Authors M. I. Shchekalev, G. V. Bokov, 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

complexitylinear ordering of verticesShannon functiontopological sortingweighted directed acyclic graphs

Mathematics Subject Classification ID

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

Recommendations

• Topological orderings of weighted directed acyclic graphs
• scientific article; zbMATH DE number 1560506
• scientific article; zbMATH DE number 4047762
• scientific article; zbMATH DE number 2099510
• Linear time algorithms to solve the linear ordering problem for oriented tree based graphs

Cites work

• scientific article; zbMATH DE number 5344975 (Why is no real title available?)
• Introduction to algorithms
• On the minimal packing of a tree with fixed vertices
• Topological orderings of weighted directed acyclic graphs

Cited in

(4)

• On an ordering problem in weighted hypergraphs
• An order approach for the core maintenance problem on edge-weighted graphs
• Topological orderings of weighted directed acyclic graphs
• Cuts of linear orders

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1980441)