Topological sorts on DAGs

DOI10.1016/J.IPL.2014.09.031zbMATH Open1304.05064OpenAlexW2061705354MaRDI QIDQ477668FDOQ477668

Junhu Wang, Chaoyi Pang, Tongliang Li, Yu Cheng, 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

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

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)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• A structured program to generate all topological sorting arrangements
• Online topological ordering
• Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
• Average-case analysis of incremental topological ordering

Cited In (3)

• Criterion for a graph to admit a good orientation in terms of leaf blocks
• Title not available (Why is that?)
• Title not available (Why is that?)

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)