A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering

DOI10.1016/J.TCS.2007.08.009MaRDI QIDQ2465638zbMATH OpenOpenAlexFDO

Authors Hsiao-Fei Liu, Kun-Mao Chao

Publication date 7 January 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.08.009

zbMATH Keywords

algorithmsonline algorithmstopological ordertight analysis

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• An algorithm for online topological ordering
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
• Online topological ordering
• Online topological ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering

Cites work

• scientific article; zbMATH DE number 432748 (Why is no real title available?)
• scientific article; zbMATH DE number 1947389 (Why is no real title available?)
• A dynamic topological sort algorithm for directed acyclic graphs
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
• Fibonacci heaps and their uses in improved network optimization algorithms
• Maintaining a topological order under edge insertions
• On competitive on-line algorithms for the dynamic priority-ordering problem
• Online topological ordering

Cited in

(5)

• Online topological ordering
• Average-Case Analysis of Online Topological Ordering
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
• An O ( n ^2.75 ) algorithm for incremental topological ordering
• An algorithm for online topological ordering

Describes a project that uses

Uses Software

• Sather
• COMET

This page was built for publication: A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering

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