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

MaRDI QIDQ4607873zbMATH OpenFDO

Authors Aaron Bernstein, Shiri Chechik

Publication date 15 March 2018

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

Mathematics Subject Classification ID

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

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

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 cycle detection, topological ordering, and strong component maintenance
• Incremental dead state detection in logarithmic time

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)