An O ( n 2.75 ) algorithm for incremental topological ordering
Deepak Ajwani, Tobias Friedrich, Ulrich Meyer · ACM Transactions on Algorithms · 2008
We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with n nodes, under an online edge insertion sequence, in O ( n 2.75 ) time, independent of the number m of edges inserted. For dense DAGs, this is an improvement over the previous best result of O (min{ m 3/2 log n , m 3/2 + n 2 log n }) by Katriel and Bodlaender [2006]. We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.