research-article

An O(n^2.75) algorithm for incremental topological ordering

Authors:

Tobias Friedrich,

Ulrich MeyerAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 4, Issue 4

Article No.: 39, Pages 1 - 14

https://doi.org/10.1145/1383369.1383370

Published: 22 August 2008 Publication History

Abstract

We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with n nodes, under an online edge insertion sequence, in O(n^2.75) time, independent of the number m of edges inserted. For dense DAGs, this is an improvement over the previous best result of O(min{m^3/2 log n, m^3/2 + n² log n}) by Katriel and Bodlaender [2006]. We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.

References

[1]

Ajwani, D., and Friedrich, T. 2007. Average-Case analysis of online topological ordering. In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 4835. Springer, 464--475.

Digital Library

[2]

Alpern, B., Hoover, R., Rosen, B. K., Sweeney, P. F., and Zadeck, F. K. 1990. Incremental evaluation of computational circuits. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 32--42.

Digital Library

[3]

Barak, A. B., and Erdős, P. 1984. On the maximal number of strongly independent vertices in a random acyclic directed graph. SIAM J. Algebr. Discr. Methods 5, 4, 508--514.

[4]

Dietz, P., and Sleator, D. 1987. Two algorithms for maintaining order in a list. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), 365--372.

Digital Library

[5]

Erdős, P., and Rényi, A. 1959. On random graphs. Publ. Math. Debrecen 6, 290--297.

[6]

Guibas, L. J. and Sedgewick, R. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 8--21.

Digital Library

[7]

Katriel, I., and Bodlaender, H. L. 2006. Online topological ordering. ACM Trans. Algor. 2, 3, 364--379.

Digital Library

[8]

Knuth, D. E., and Szwarcfiter, J. L. 1974. A structured program to generate all topological sorting arrangements. Inf. Process. Lett. 2, 6, 153--157.

[9]

Liu, H.-F., and Chao, K.-M. 2007. A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering. Theor. Comput. Sci. 389, 1-2, 182--189.

Digital Library

[10]

Marchetti-Spaccamela, A., Nanni, U., and Rohnert, H. 1993. On-Line graph algorithms for incremental compilation. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 790. Springer, 70--86.

Digital Library

[11]

Marchetti-Spaccamela, A., Nanni, U., and Rohnert, H. 1996. Maintaining a topological order under edge insertions. Inf. Process. Lett. 59, 1, 53--58.

Digital Library

[12]

Omohundro, S. M., Lim, C.-C., and Bilmes, J. 1992. The Sather language compiler/debugger implementation. Tech. rep. TR-92-017, International Computer Science Institute, Berkeley, California.

[13]

Östlin, A., and Pagh, R. 2003. Uniform hashing in constant time and linear space. In Proceedings of the 35th Symposium on Theory of Computing (STOC). ACM, 622--628.

Digital Library

[14]

Pearce, D. J., and Kelly, P. H. J. 2006. A dynamic topological sort algorithm for directed acyclic graphs. J. Exp. Algor. 11, 1.7.

Digital Library

[15]

Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2003. Online cycle detection and difference propagation for pointer analysis. In Proceedings of the 3rd International IEEE Workshop on Source Code Analysis and Manipulation (SCAM).

[16]

Ramalingam, G., and Reps, T. W. 1994. On competitive on-line algorithms for the dynamic priority-ordering problem. Inf. Process. Lett. 51, 155--161.

Digital Library

[17]

Tarjan, R. E. 1972. Depth-First search and linear graph algorithms. SIAM J. Comput. 1, 2, 146--160.

Digital Library

Cited By

Chen LKyng RLiu YMeierhans SProbst Gutenberg MMohar BShinkar IO'Donnell R(2024)Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost FlowProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649745(1165-1173)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649745
Fan HSun ZHe F(2023)Satisfiability Modulo Ordering Consistency Theory for SC, TSO, and PSO Memory ModelsACM Transactions on Programming Languages and Systems10.1145/357983545:1(1-37)Online publication date: 3-Mar-2023
https://dl.acm.org/doi/10.1145/3579835
He FSun ZFan HFreund SYahav E(2021)Satisfiability modulo ordering consistency theory for multi-threaded program verificationProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454108(1264-1279)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454108
Show More Cited By

Index Terms

An O(n^2.75) algorithm for incremental topological ordering
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m^3/2) time. For sparse graphs (m/n = ...
Online topological ordering

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/2logn, m^3/2 + n²logn}) time, an improvement over the best known result of O(mn). In addition, we ...
A faster algorithm for computing the girth of planar and bounded genus graphs

The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n^5/4 log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n²) algorithm for this problem. We also extend our results for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 4, Issue 4

August 2008

264 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1383369

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 August 2008

Accepted: 01 April 2008

Revised: 01 February 2008

Received: 01 October 2006

Published in TALG Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
574
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen LKyng RLiu YMeierhans SProbst Gutenberg MMohar BShinkar IO'Donnell R(2024)Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost FlowProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649745(1165-1173)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649745
Fan HSun ZHe F(2023)Satisfiability Modulo Ordering Consistency Theory for SC, TSO, and PSO Memory ModelsACM Transactions on Programming Languages and Systems10.1145/357983545:1(1-37)Online publication date: 3-Mar-2023
https://dl.acm.org/doi/10.1145/3579835
He FSun ZFan HFreund SYahav E(2021)Satisfiability modulo ordering consistency theory for multi-threaded program verificationProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454108(1264-1279)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454108
Olgac E(2021)Topology and Structure of Directed Acyclic GraphsAdvances in Information and Communication10.1007/978-3-030-73103-8_23(335-351)Online publication date: 16-Apr-2021
https://doi.org/10.1007/978-3-030-73103-8_23
Bernstein AChechik SCzumaj A(2018)Incremental topological sort and cycle detection in [Equation] expected total timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175268(21-34)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175268
Bender MFineman JGilbert STarjan R(2015)A New Approach to Incremental Cycle Detection and Related ProblemsACM Transactions on Algorithms10.1145/275655312:2(1-22)Online publication date: 8-Dec-2015
https://dl.acm.org/doi/10.1145/2756553
Wang GChen SZhang XZhou Z(2012)Topological ordering algorithm for LDAGInformation Processing Letters10.1016/j.ipl.2012.07.015112:21(823-828)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.ipl.2012.07.015
Ajwani DFriedrich T(2010)Average-case analysis of incremental topological orderingDiscrete Applied Mathematics10.1016/j.dam.2009.07.006158:4(240-250)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1016/j.dam.2009.07.006

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents