Abstract
Consider a dynamic forest of unrooted trees over a set of n vertices which we update by link operations: Each link operation adds a new edge adjacent to vertices in two different trees. Every edge in the forest has a weight associated with it, and at any time we want to be able to answer a path-min query which returns that edge of minimum weight along the path between two given vertices.
For the case where the weights are integers we give an algorithm that performs n − 1 link operations and m pathmin queries in O(n + mα(m,n)) time. This extends well known results of Tarjan [11] and Yao [12] to a more general dynamic setting at the cost of restricting the weights to be integers. We also suggest a simpler data structures for the case where trees are rooted and the link operation always adds an edge between the root of one tree and an arbitrary vertex of another tree.
This work is partially supported by United States - Israel Binational Science Foundation, project number 2006204.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report Tech. Report 71/87, Tel Aviv University
Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Welzl, E., Montanari, U., Rolim, J. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 73–84. Springer, Heidelberg (2000)
Chazelle, B., Rosenberg, B.: The complexity of computing partial sums off-line. Int. J. Comput. Geometry Appl. 1(1), 33–45 (1991)
Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533–551 (1994)
Gabow, H.N.: A scaling algorithm for weighted matching on general graphs. In: FOCS, pp. 90–100 (1985)
Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: SODA, pp. 434–443 (1990)
Georgiadis, L., Kaplan, H., Shafrir, N., Tarjan, R.E., Werneck, R.F.: Data structures for mergeable trees (2007), http://arxiv.org/abs/0711.1682v1
Georgiadis, L., Tarjan, R.E., Werneck, R.F.: Design of data structures for mergeable trees. In: SODA, pp. 394–403 (2006)
Kaplan, H., Shafrir, N.: Finding path minima in incremental unrooted trees. Technical report, http://www.cs.tau.ac.il/~haimk/papers/pathmin.pdf
La Poutre, J.A.: New techniques for the union-find problem. In: SODA, pp. 54–63 (1990)
Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM 26(4), 690–715 (1979)
Yao, A.C.: Space-time tradeoff for answering range queries (extended abstract). In: STOC, pp. 128–136 (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kaplan, H., Shafrir, N. (2008). Path Minima in Incremental Unrooted Trees . In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_47
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)