An O ( n 2.75 ) algorithm for incremental topological ordering

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.