Maintaining Center and Median in Dynamic Trees

1. A. Kanevsky, R Tamassia, G. Battista, and J. Chen. On-line maintenance of the four-connected components of a graph (extended abstract). In 32nd FOCS, pages 793–801, 1991.

   Google Scholar 

2. S. Alstrup, J. Holm, K de Lichtenberg, and M. Thorup. Minimizing diameters of dynamic trees. In ICALP’97, pages 270–280, 1997.

   Google Scholar 

3. V. Auletta, D. Parente, and G. Persiano. Dynamic and static algorithms for optimal placement of resources in a tree. TCS, 165:441–461, 1996.

   Article  MATH  MathSciNet  Google Scholar 

4. G. Battista and R. Tamassia. Incremental planarity testing (extended abstract). In 30th FOCS, pages 436–441, 1989.

   Google Scholar 

5. G. Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. In ICALP’90, pages 598–611, 1990.

   Google Scholar 

6. S. Cheng and M. Ng. Isomorphism testing and display of symmetries in dynamic trees. In Proc. 7th SODA, 1996.

   Google Scholar 

7. R. Cohen and R. Tamassia. Dynamic expression trees. Algorithmica, 13(3):245–265, 1995.

   Article  MATH  MathSciNet  Google Scholar 

8. R. Cohen and R. Tamassia. Combine and conquer. Algorithmica, 18(3):324–362, 1997.

   Article  MathSciNet  Google Scholar 

9. R. F. Cohen and R. Tamassia. Dynamic expression trees and their applications. In 2nd SODA, pages 52–61, 1991.

   Google Scholar 

10. G. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SICOMP, 14(4):781–798, 1985.

    MATH  MathSciNet  Google Scholar 

11. G. Frederickson. Parametric search and locating supply centers in trees. In WADS’91, volume 519 of LNCS, pages 299–319, 1991.

    Google Scholar 

12. G. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SICOMP, 26(2):484–538, 1997. See also FOCS’91.

    MATH  MathSciNet  Google Scholar 

13. M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st STOC, pages 345–354, 1989.

    Google Scholar 

14. Z. Galil and G. Italiano. Maintaining biconnected components of dynamic planar graphs. In ICALP’91, 1991.

    Google Scholar 

15. B. Gavish and S. Sridhar. Computing the 2-median on tree networks in O(n log n) time. Networks, 26, 1995. See also Networks Vol. 27, 1996.

    Google Scholar 

16. A. Goldberg, M. Grigoriadis, and R. Tarjan. Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Programming, 50:277–290, 1991.

    Article  MATH  MathSciNet  Google Scholar 

17. A. Goldman. Optimal center location in simple networks. Transportation Sci., 5:212–221, 1971.

    MathSciNet  Google Scholar 

18. S. Hakimi and O. Kariv. An algorithmic approach to network location problems, ii: the p-medians. SIAM J. APPL. MATH., 37(3):539–560, 1979.

    Article  MATH  MathSciNet  Google Scholar 

19. G. Handler. Minimax location of a facility in an undirected tree network. Transportation. Sci., 7:287–293, 1973.

    Article  MathSciNet  Google Scholar 

20. M. R. Henzinger and V. King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Proc. 27th Symp. on Theory of Computing, pages 519–527, 1995.

    Google Scholar 

21. J. A. La Poutré. Dynamic graph algorithms and data structures. PhD thesis, Dep. Comp. Sci., Utrecht Uni., 1991.

    Google Scholar 

22. S. Peckham. Maintaining tree projections in amortized O(log n) time. Technical Report TR89-1034, Cornell Uni., Comp. Sci. Dep., 1989.

    Google Scholar 

23. J. A. L. Poutré. Alpha-algorithms for incremental planarity testing. In 26th STOC, pages 706–715, 1994.

    Google Scholar 

24. J. L. Poutré. Maintenance of triconnected components of graphs. In ICALP’92, volume 623 of LNCS, pages 354–365, 1992.

    Google Scholar 

25. T. Radzik. Implementations of dynamic trees with in-subtree operations. ACM J. Experimental Algorithmics, 3:Article 9, 1998.

    Google Scholar 

26. A. Rosenthal and J. Pino. A generalized algorithm for centrality problems on trees. J. ACM, 36:349–361, 1989.

    Article  MATH  MathSciNet  Google Scholar 

27. D. Sleator and R. Tarjan. A data structure for dynamic trees. JCSS, 26(3):362–391, 1983. See also STOC’81.

    MATH  MathSciNet  Google Scholar 

28. R. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of computer and system sciences, 18(2):110–127, 1979. See also STOC 1977.

    Article  MATH  MathSciNet  Google Scholar 

29. R. Tarjan. Dynamic trees and search trees via euler tours, applied to the network simplex algorithm. Technical Report 503–95, Dep. Comp. Sci., Princeton Uni., September 1995.

    Google Scholar 

30. J. Westbrook and R. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7:433–464, 1992.

    Article  MathSciNet  MATH  Google Scholar 

Download references