An Õ(n 2.5 )-Time Algorithm for Online Topological Ordering
Hsiao-Fei Liu, Kun‐Mao Chao · 2008
We present an Õ(n2.5)-time algorithm for maintaining the topological order of a directed acyclic graph with n vertices while inserting m edges. This is an improvement over the previous result of O(n 2.75) by Ajwani, Friedrich, and Meyer. 1