A new approach to incremental topological ordering

ABSTRACT

Let G = (V, E) be a directed acyclic graph (dag) with n = |V| and m = |E|. We say that a total ordering ≺ on vertices V is a topological ordering if for every edge (u, v) ∈ E, we have u ∈ v. In this paper, we consider the problem of maintaining a topological ordering subject to dynamic changes to the underlying graph. That is, we begin with an empty graph G = (V, ø) consisting of n nodes. The adversary adds m edges to the graph G, one edge at a time. Throughout this process, we maintain an online topological ordering of the graph G.

In this paper, we present a new algorithm that has a total cost of O(n²logn) for maintaining the topological ordering throughout all the edge additions. At the heart of our algorithm is a new approach for maintaining the ordering. Instead of attempting to place the nodes in an ordered list, we assign each node a label that is consistent with the ordering, and yet can be updated efficiently as edges are inserted. When the graph is dense, our algorithm is more efficient than existing algorithms. By way of contrast, the best known prior algorithms achieve only O(min(m^1.5, n^2.5)) cost.

REFERENCES

• 1: D. Ajwani and T. Friedrich. Average-case analysis of online topological ordering. In T. Tokuyama, editor, ISAAC, volume 4835 of Lecture Notes in Computer Science, pages 464--475. Springer, 2007.
• 2: D. Ajwani, T. Friedrich, and U. Meyer. An O(n^2.75) algorithm for online topological ordering. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, volume 4059 of Lecture Notes in Computer Science, pages 53--64. Springer, 2006.
• 3: 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
• 4: Ferenc Belik, An Efficient Deadlock Avoidance Technique, IEEE Transactions on Computers, v.39 n.7, p.882-888, July 1990 [doi>10.1109/12.55690]
• 5: 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
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 8: Bernhard Haeupler , Telikepalli Kavitha , Rogers Mathew , Siddhartha Sen , Robert E. Tarjan, Faster Algorithms for Incremental Topological Ordering, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_35]
• 9: B. Haeupler, S. Sen, and R. E. Tarjan. Incremental topological ordering and strong component maintenance. CoRR, abs/0803.0792, 2008.
• 10: I. Katriel. On algorithms for online topological ordering and sorting. Technical Report MPI-I-2004-1-003, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 2004.
• 11: Irit Katriel , Hans L. Bodlaender, Online topological ordering, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 12: T. Kavitha and R. Mathew. Faster algorithms for online topological ordering. CoRR, abs/0711.0251, 2007.
• 13: Hsiao-Fei Liu , Kun-Mao Chao, A tight analysis of the Katriel–Bodlaender algorithm for online topological ordering, Theoretical Computer Science, v.389 n.1-2, p.182-189, December, 2007 [doi>10.1016/j.tcs.2007.08.009]
• 14: 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
• 15: 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]
• 16: S. M. Omohundro, C. Lim, and J. Bilmes. The sather language compiler/debugger implementation. Technical report, International Computer Science Institute, Berkeley, March 1992.
• 17: D. Pearce, P. Kelly, and C. Hankin. Online cycle detection and difference propagation for pointer analysis. In Proceedings of the 3rd International Workshop on Source Code Analysis and Manipulation, pages 3--12, Sept. 2003.
• 18: D. J. Pearce and P. H. J. Kelly. A dynamic algorithm for topologically sorting directed acyclic graphs. In Proceedings of the 3rd International Workshop on Efficient Experimental Algorithms, volume 3059 of Lecture Notes in Computer Science, pages 383--398. Springer, 2004.
• 19: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms