An algorithm for online topological ordering

DOI10.1016/J.ENDM.2006.06.050MaRDI QIDQ3439455zbMATH OpenOpenAlexFDO

Authors Deepak Ajwani, Tobias Friedrich, Ulrich Meyer

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2006.06.050

zbMATH Keywords

graph algorithmsonline algorithmstopological ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• An ${\cal O}(n^{2.75})$ 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

Cites work

• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• Maintaining a topological order under edge insertions
• On competitive on-line algorithms for the dynamic priority-ordering problem
• Online topological ordering

Cited in

(7)

• On-line sorting of twisted sequences in linear time
• A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering
• Online topological ordering
• Online topological ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• Average-Case Analysis of Online Topological Ordering
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering

Describes a project that uses

Uses Software

• Sather

This page was built for publication: An algorithm for online topological ordering

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