AbstractConsider a tree T with a number of extra edges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p, no edge that is on the unique path (in T) between the endpoints of b is also in p or on the unique path between the two endpoints of any other bridge in p. (Such a path is called non-reversing.) We investigate the trade-off between the number of added bridges and the resulting diameter. Upper and lower bounds of the same order are obtained for all diameters of constant size. For the special case where T is a chain we also obtain matching upper and lower bounds for diameters of size alpha(N) + O(1) or of size f(N) where f(N) grows faster than alpha(N). Some applications are given.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures
Selected papers that cite this one
- Mikkel Thorup. Parallel shortcutting of rooted trees. Journal of Algorithms, 23(1):139-159, April 1997.
Selected references
- Maria Luisa Bonet and Samuel R. Buss. The serial transitive closure problem for trees. SIAM Journal on Computing, 24(1):109-122, February 1995.
- Bernard Chazelle. Computing on a free tree via complexity-preserving mappings. Algorithmica, 2:337-361, 1987.
- Robert Endre Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26(4):690-715, October 1979.
- Andrew C. Yao. Space-time tradeoff for answering range queries (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 128-136, San Francisco, California, 5-7 May 1982.