Topological ordering algorithm for LDAG

DOI10.1016/J.IPL.2012.07.015MaRDI QIDQ456140zbMATH OpenOpenAlexFDO

Authors Guiping Wang, Zhen Zhou, Shuyu Chen, Xiaoqin Zhang

Publication date 23 October 2012

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

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

zbMATH Keywords

computational complexityDAGLDAGleveltopological order

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A dynamic topological sort algorithm for directed acyclic graphs
• Topological sorts on DAGs
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Maintaining a topological order under edge insertions
• A new approach to incremental topological ordering

Cites work

• A structured program to generate all topological sorting arrangements
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Introduction to algorithms
• On-demand minimum cost benchmarking for intermediate dataset storage in scientific cloud workflow systems

Cited in

(3)

• Topological sorts on DAGs
• Evaluating topological ordering in directed acyclic graphs
• The topological ordering of covering nodes

This page was built for publication: Topological ordering algorithm for LDAG

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