Topological sorts on DAGs

DOI10.1016/j.ipl.2014.09.031zbMath1304.05064OpenAlexW2061705354MaRDI QIDQ477668

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

zbMATH Keywords

BFSdirected acyclic graphgraph algorithmsdepth-first searchbreadth-first searchDFStopological orderingDAGtopological sort

Mathematics Subject Classification ID

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

Related Items (1)

Criterion for a graph to admit a good orientation in terms of leaf blocks

Cites Work

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

This page was built for publication: Topological sorts on DAGs