An $\tilde{O}(n^{2.5})$-Time Algorithm for Online Topological Ordering

Hsiao-Fei Liu, Kun-Mao Chao

We present an $\tilde{O}(n^{2.5})$-time algorithm for maintaining the topological order of a directed acyclic graph with $n$ vertices while inserting $m$ edges.