A dynamic topological sort algorithm for directed acyclic graphs

DOI10.1145/1187436.1210590zbMath1143.05334OpenAlexW2084763084MaRDI QIDQ3507767

David J. Pearce, Paul H. J. Kelly

Publication date: 20 June 2008

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.205.2688

Mathematics Subject Classification ID

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

Related Items (9)

\textit{Graph\_sampler}: a simple tool for fully Bayesian analyses of DAG-models ⋮ Heuristic approaches for scheduling jobs in large-scale flexible job shops ⋮ Space-aware reconfiguration ⋮ A batch-oblivious approach for complex job-shop scheduling problems ⋮ Average-Case Analysis of Online Topological Ordering ⋮ A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering ⋮ Average-case analysis of incremental topological ordering ⋮ Space-Aware Reconfiguration ⋮ An Optimal Constraint Programming Approach to the Open-Shop Problem

Cites Work

• Maintaining longest paths incrementally
• Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs
• On incremental evaluation of ordered attributed grammars
• On competitive on-line algorithms for the dynamic priority-ordering problem
• On the computational complexity of dynamic graph problems
• Improved algorithms for dynamic shortest paths
• Maintaining a topological order under edge insertions
• Bounded incremental computation
• A random graph model for massive graphs
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• Random Generation of Directed Acyclic Graphs
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• Separator based sparsification for dynamic planar graph algorithms
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
• A fully dynamic algorithm for maintaining the transitive closure
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A dynamic topological sort algorithm for directed acyclic graphs