Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure | Algorithmica Skip to main content
Springer Nature Link
Log in

Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n 2) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Ω(n 2) entries of this matrix, no better bounds are possible for this class of algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)

    MATH  Google Scholar 

  2. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251–280 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  3. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  4. Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: breaking through the O(n 2) barrier. In: Proc. of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS’00), pp. 381–389 (2000)

  5. Demetrescu, C., Italiano, G.F.: Trade-offs for fully dynamic reachability on dags: breaking through the O(n 2) barrier. J. Assoc. Comput. Mach. (J. ACM) 52(2), 147–156 (2005)

    MathSciNet  Google Scholar 

  6. Even, S., Shiloach, Y.: An on-line edge-deletion problem. J. ACM 28, 1–4 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  7. Fischer, M.J., Meyer, A.R.: Boolean matrix multiplication and transitive closure. In: Conference Record 1971 Twelfth Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, 13–15 October 1971, pp. 129–131. IEEE

  8. Furman, M.E.: Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Sov. Math. Dokl. 11(5) (1970). English translation

  9. Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS’95), pp. 664–672 (1995)

  10. Ibaraki, T., Katoh, N.: On-line computation of transitive closure for graphs. Inf. Process. Lett. 16, 95–97 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  11. Italiano, G.F.: Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci. 48(2–3), 273–281 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  12. Italiano, G.F.: Finding paths and deleting edges in directed acyclic graphs. Inf. Process. Lett. 28, 5–11 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  13. Khanna, S., Motwani, R., Wilson, R.H.: On certificates and lookahead in dynamic graph problems. Algorithmica 21(4), 377–394 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  14. King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS’99), pp. 81–99 (1999)

  15. King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure. J. Comput. Syst. Sci. 65(1), 150–167 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  16. La Poutré, J.A., van Leeuwen, J.: Maintenance of transitive closure and transitive reduction of graphs. In: Proc. Workshop on Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 314, pp. 106–120. Springer, Berlin (1988)

    Google Scholar 

  17. Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04), pp. 248–255 (2004)

  18. Munro, I.: Efficient determination of the transitive closure of a directed graph. Inf. Process. Lett. 1(2), 56–58 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  19. Roditty, L.: A faster and simpler fully dynamic transitive closure. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, USA, pp. 404–412 (2003)

  20. Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04), Rome, Italy, pp. 509–517 (2004)

  21. Sankowski, P.: Subquadratic algorithm for dynamic shortest distances. In: Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON’05), pp. 461–470 (2005)

  22. Yellin, D.M.: Speeding up dynamic transitive closure for bounded degree graphs. Acta Inf. 30, 369–384 (1993)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Rome, Italy

    Camil Demetrescu

  2. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Rome, Italy

    Giuseppe F. Italiano

Authors
  1. Camil Demetrescu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giuseppe F. Italiano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Camil Demetrescu.

Additional information

This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented at the 41st Annual Symp. on Foundations of Computer Science, 2000.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Demetrescu, C., Italiano, G.F. Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure. Algorithmica 51, 387–427 (2008). https://doi.org/10.1007/s00453-007-9051-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9051-4

Keywords

Search

Navigation