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

DOI10.1016/J.TCS.2007.08.009zbMATH Open1143.68067OpenAlexW2068283945MaRDI QIDQ2465638FDOQ2465638

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

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

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)

Cites Work

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

Cited In (5)

• 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
• Online topological ordering
• Average-Case Analysis of Online Topological Ordering

Uses Software

• COMET
• Sather

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)