MAINTAINING A TOPOLOGICAL ORDER UNDER EDGE INSERTIONS

A topological order of the vertices of a directed acyclic graph G = (V ,E) is any total order ord such that if (x, y) is an element of E, the n x precedes y in ord. In this paper we consider the dynamic version o f this problem, and provide simple algorithms and data structures achi eving O(n) amortized time per edge insertion starting from an empty gr aph, which favorably compares to the trivial O(m+n) time bound per ope ration obtained applying the off-line algorithm. The additional space requirement, beside the representation of the graph itself, is O(n). E xperimental results show that our algorithm performs in practice order s of magnitude faster than the off-line algorithm.