Incremental topological sort and cycle detection in O(m n) expected total time

zbMATH Open1402.68138MaRDI QIDQ4607873FDOQ4607873

Authors: Aaron Bernstein, Shiri Chechik 

Publication date: 15 March 2018

Full work available at URL: http://dl.acm.org/citation.cfm?id=3175268

Recommendations

• A new approach to incremental cycle detection and related problems
• Faster Algorithms for Incremental Topological Ordering
• Incremental cycle detection, topological ordering, and strong component maintenance
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Online topological ordering

Mathematics Subject Classification ID

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

Cited In (7)

• Faster Algorithms for Incremental Topological Ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Decremental strongly connected components and single-source reachability in near-linear time
• Space-aware reconfiguration
• A new approach to incremental cycle detection and related problems
• Incremental dead state detection in logarithmic time
• Incremental cycle detection, topological ordering, and strong component maintenance

This page was built for publication: Incremental topological sort and cycle detection in \(\tilde O(m \sqrt n)\) expected total time

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