Maintaining a Topological Order Under Edge Insertions
Lists
Only you see this
Abstract
A topological order of the vertices of a directed acyclic graph $G = (V,E)$ is any total order ord such that if $(x,y) ϵ E$, then $x \text{ precedes} y$ in ord. In this paper we consider the dynamic version of this problem, and provide simple algorithms and data structures achieving $O(n)$ amortized time per edge insertion starting from an empty graph, which favorably compares to the trivial $O(m + n)$ time bound per operation obtained applying the off-line algorithm. The additional space requirement, beside the representation of the graph itself, is $O(n)$. Experimental results show that our algorithm performs in practice orders of magnitude faster than the off-line algorithm.
BibTeX
@article{marchettispaccamela1996maintaining,
author = {Alberto Marchetti-Spaccamela and Umberto Nanni and Hans Rohnert},
title = {{Maintaining a Topological Order Under Edge Insertions}},
journal = {Inf. Process. Lett.},
year = {1996},
doi = {10.1016/0020-0190(96)00075-0},
}Loading related content...