An {\cal O}(n^{2.75}) Algorithm for Online Topological Ordering

DOI10.1007/11785293_8MaRDI QIDQ5757899zbMATH OpenOpenAlexFDO

Authors Deepak Ajwani, Tobias Friedrich, Ulrich Meyer

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_8

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• An algorithm for online topological ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Online topological ordering
• Online topological ordering
• A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering

Cited in

(10)

• Online topological ordering
• Average-Case Analysis of Online Topological Ordering
• Maintaining a topological order under edge insertions
• A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• An algorithm for online topological ordering
• Average-case analysis of incremental topological ordering
• On-line sorting of twisted sequences in linear time
• A new approach to incremental topological ordering
• A dynamic topological sort algorithm for directed acyclic graphs

This page was built for publication: An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering

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