An O(n2.75) algorithm for online topological ordering 1

We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n2.75) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of Katriel and Bodlaender.