Updating Directed Minimum Cost Spanning Trees

  • Gerasimos G. Pollatos
  • Orestis A. Telelis
  • Vassilis Zissimopoulos
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4007)


We consider the problem of updating a directed minimum cost spanning tree (DMST), when edges are deleted from or inserted to a weighted directed graph. This problem apart from being a classic for directed graphs, is to the best of our knowledge a wide open aspect for the field of dynamic graph algorithms. Our contributions include results on the hardness of updates, a dynamic algorithm for updating a DMST, and detailed experimental analysis of the proposed algorithm exhibiting a speedup factor of at least 2 in comparison with the static practice.


branchings dynamic graph algorithms data structures 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Edmonds, J.: Optimum branchings. Journal of Research of the National Bureau for Standards 69B, 125–130 (1967)MathSciNetGoogle Scholar
  2. 2.
    Kang, I., Poovendran, R.: Maximizing network lifetime of broadcasting over wireless stationary adhoc networks. Mobile Networks 11 (to appear, 2006)Google Scholar
  3. 3.
    Li, N., Hou, J.: Topology Control in Heterogeneous Wireless Networks: Problems and Solutions. In: Proceedings of the 23rd IEEE INFOCOM (2004)Google Scholar
  4. 4.
    Li, Z., Hauck, S.: Configuration compression for virtex fpgas. In: Proceedings of the 9th IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2001, pp. 147–159 (2001)Google Scholar
  5. 5.
    He, L., Mitra, T., Wong, W.: Configuration bitstream compression for dynamically reconfigurable FPGAs. In: Proceedings of the 2004 International Conference on Computer-Aided Design, ICCAD 2004, pp. 766–773 (2004)Google Scholar
  6. 6.
    Bock, F.: An algorithm to construct a minimum spanning tree in a directed network. In: Developments in Operations Research. Gordon and Breach, pp. 29–44 (1971)Google Scholar
  7. 7.
    Chu, Y.J., Liu, T.H.: On the shortest arborescence of a directed graph. Scientia Sinica 14, 1396–1400 (1965)MathSciNetzbMATHGoogle Scholar
  8. 8.
    Tarjan, R.E.: Finding optimum branchings. Networks 7, 25–35 (1977)CrossRefMathSciNetzbMATHGoogle Scholar
  9. 9.
    Gabow, H.N., Galil, Z., Spencer, T.H., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109–122 (1986)CrossRefMathSciNetzbMATHGoogle Scholar
  10. 10.
    Mendelson, R., Tarjan, R.E., Thorup, M., Zwick, U.: Melding Priority Queues. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 223–235. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  11. 11.
    Eppstein, D., Galil, Z., Italiano, G.F.: 8: Dynamic graph algorithms. In: Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton (1999)Google Scholar
  12. 12.
    Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM 48, 723–760 (2001)CrossRefMathSciNetzbMATHGoogle Scholar
  13. 13.
    Alpern, B., Hoover, R., Rosen, B.K., Sweeney, P.F., Zadeck, F.K.: Incremental evaluation of computational circuits. In: Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 32–42 (1990)Google Scholar
  14. 14.
    Ramalingam, G., Reps, T.: On the complexity of dynamic graph problems. Theoretical Computer Science 158(1&2), 233–277 (1996)CrossRefMathSciNetzbMATHGoogle Scholar
  15. 15.
    Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms 34, 251–281 (2000)CrossRefMathSciNetzbMATHGoogle Scholar
  16. 16.
    Pearce, D.J., Kelly, P.H.J.: A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol. 3059, pp. 383–398. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  17. 17.
    Spira, P.M., Pan, A.: On Finding and Updating Spanning Trees and Shortest Paths. SIAM Journal on Computing 4(3), 364–380 (1975)CrossRefMathSciNetGoogle Scholar
  18. 18.
    Rabin, M.O.: Proving simultaneous positivity of linear forms. Journal of Computers and Systems Sciences 6, 639–650 (1972)CrossRefMathSciNetzbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Gerasimos G. Pollatos
    • 1
  • Orestis A. Telelis
    • 1
  • Vassilis Zissimopoulos
    • 1
  1. 1.Dept. of Informatics and TelecommunicationsUniversity of AthensHellasGreece

Personalised recommendations