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

DOI10.1016/j.tcs.2007.08.009zbMath1143.68067OpenAlexW2068283945MaRDI QIDQ2465638

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

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

Uses Software

• COMET
• Sather

Cites Work

• Unnamed Item
• Unnamed Item
• On competitive on-line algorithms for the dynamic priority-ordering problem
• Maintaining a topological order under edge insertions
• Online topological ordering
• A dynamic topological sort algorithm for directed acyclic graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering

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