Maintaining a topological order under edge insertions

DOI10.1016/0020-0190(96)00075-0zbMath1046.68651OpenAlexW2008593246MaRDI QIDQ1847369

Umberto Nanni, Hans Rohnert, Alberto Marchetti-Spaccamela

Publication date: 24 June 2003

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

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00075-0

zbMATH Keywords

directed acyclic graph

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

Characterization of super-stable matchings ⋮ Accelerating the calculation of makespan used in scheduling improvement heuristics ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ 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 ⋮ Semi-dynamic breadth-first search in digraphs ⋮ An algorithm for online topological ordering

Uses Software

• LEDA
• Sather

Cites Work

• Amortized efficiency of a path retrieval data structure
• Finding paths and deleting edges in directed acyclic graphs
• Speeding up dynamic transitive closure for bounded degree graphs
• Amortized Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maintaining a topological order under edge insertions