Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs

DOI10.1016/J.IPL.2003.07.005MaRDI QIDQ1029013zbMATH OpenOpenAlexFDO

Authors J. Blot

Publication date 9 July 2009

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

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

zbMATH Keywords

DAGgraph algorithmsincremental updatingspace complexitytopological sorting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• A dynamic topological sort algorithm for directed acyclic graphs
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Faster Algorithms for Incremental Topological Ordering
• A new approach to incremental topological ordering
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs

Cites work

• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• On competitive on-line algorithms for the dynamic priority-ordering problem
• Solving systems of difference constraints incrementally

Cited in

(3)

• A dynamic topological sort algorithm for directed acyclic graphs
• Topological ordering algorithm for LDAG
• Engineering a Topological Sorting Algorithm for Massive Graphs

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs

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