Topological sorts on DAGs

DOI10.1016/J.IPL.2014.09.031MaRDI QIDQ477668zbMATH OpenOpenAlexFDO

Authors Chaoyi Pang, Junhu Wang, Yu Cheng, Tongliang Li, Hao Lan Zhang

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.09.031

zbMATH Keywords

BFSdirected acyclic graphbreadth-first searchdepth-first searchgraph algorithmsDFStopological orderingDAGtopological sort

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Recommendations

• A dynamic topological sort algorithm for directed acyclic graphs
• scientific article; zbMATH DE number 3958742
• scientific article; zbMATH DE number 522854
• On the complexity of topological sorting
• Topological ordering algorithm for LDAG

Cites work

• A structured program to generate all topological sorting arrangements
• Average-case analysis of incremental topological ordering
• Depth-First Search and Linear Graph Algorithms
• Incremental cycle detection, topological ordering, and strong component maintenance
• Online topological ordering

Cited in

(4)

• Criterion for a graph to admit a good orientation in terms of leaf blocks
• Topological ordering algorithm for LDAG
• scientific article; zbMATH DE number 7376042 (Why is no real title available?)
• scientific article; zbMATH DE number 522854 (Why is no real title available?)

This page was built for publication: Topological sorts on DAGs

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