Online topological ordering

ABSTRACT

It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O(min{m^{3/2 log n m3/3} + n² log n}) time, an improvement over the best known result of O(mn). In addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. We show that the algorithm runs in time O(mk log² n) for general k and that it can be implemented to run in O(n log n) time on trees, which is optimal. If the input contains cycles, the algorithm detects this.

REFERENCES

• 1: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• 2: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton , Jack Zito, Two Simplified Algorithms for Maintaining Order in a List, Proceedings of the 10th Annual European Symposium on Algorithms, p.152-164, September 17-21, 2002
• 3: Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4]
• 4: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 5: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 6: I. Katriel. On algorithms for online topological ordering and sorting. Research Report MPI-I-2004-1-003, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 2004.
• 7: Alberto Marchetti-Spaccamela , Umberto Nanni , Hans Rohnert, On-line Graph Algorithms for Incremental Compilation, Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, p.70-86, June 16-18, 1993
• 8: Alberto Marchetti-Spaccamela , Umberto Nanni , Hans Rohnert, Maintaining a topological order under edge insertions, Information Processing Letters, v.59 n.1, p.53-58, July 8, 1996 [doi>10.1016/0020-0190(96)00075-0]
• 9: S. M. Omohundro, C. Lim, and J. Bilmes. The Sather language compiler/debugger implementation. Technical Report TR-92-017, International Computer Science Institute, Berkeley, March 1992.
• 10: D. J. Pearce and P. H. J. Kelly. A dynamic algorithm for topologically sorting directed acyclic graphs. In Proc. of the 3rd Int. Worksh. Efficient and Experimental Algorithms (WEA 2004), Lecture Notes in Computer Science. Springer-Verlag, 2004.
• 11: G. Ramalingam , Thomas Reps, On competitive on-line algorithms for the dynamic priority-ordering problem, Information Processing Letters, v.51 n.3, p.155-161, Aug. 10, 1994 [doi>10.1016/0020-0190(94)00080-8]
• 12: G. Ramalingam , Thomas Reps, On the computational complexity of dynamic graph problems, Theoretical Computer Science, v.158 n.1-2, p.233-277, May 20, 1996 [doi>10.1016/0304-3975(95)00079-8]
• 13: N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309--322, 1986.
• 14: R. E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146--160, June 1972.