Abstract
The p-median problem on a tree T is to find a set S of p vertices on T that minimize the sum of distances from T’s vertices to S. For this problem, Tamir [12] had an O(pn 2)-time algorithm, while Gavish and Sridhar [1] had an O(nlog n)-time algorithm for the case of p=2. Wang et al. [13] introduced two generalizations by imposing constraints on the 2-median: one is to limit their distance while the other is to limit their eccentricity, and they had O(n2)-time algorithms for both. We solve both generalizations in O(nlog n) time, matching even the fastest algorithm currently known for the 2-median problem. We also study cases when linear time algorithms exist for the 2-median problem and the two generalizations. For example, we solve all three in linear time when edge lengths and vertex weights are all polynomially bounded integers. Finally, we consider the relaxation of the two generalized problems by allowing 2-medians on any position of edges, instead of just on vertices, and we give O(nlog n)-time algorithms for them.
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
B. Gavish and S. Sridhar, Computing the 2-median on tree networks in O(nlg n) time, Networks, vol. 26, pp. 305–317, 1995.
S. L. Hakimi, Optimal distribution of switching centers in communication networks and some related graph theoretical problems, Operations Research, vol. 13, pp. 462–475, 1965.
H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union, Journal of Computer and System Sciences, vol. 30, pp. 209–221, 1985.
Z. Galil and G. F. Italino, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys, vol. 23, no. 3, pp. 319–344, 1991.
A. J. Goldman, Optimal center location in simple networks, Transportation science, vol. 5, pp. 212–221, 1971.
G. Y. Handler and P. Mirchandani, Location on Networks, MIT Press, Cambridge, MA, 1979.
J. JáJá, An Introduction to Parallel Algorithm, Addison-Wesley, Reading, MA, 1992.
O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems, Part II: The p-medians, SIAM Journal on Applied Mathematics, vol. 37, pp. 539–560, 1979.
S.-C. Ku, Algorithms for location problems on trees, Ph.D. thesis, Computer Science Department, National Tsing Hua University, 2001.
P. B. Mirchandani and A. Oudjit, Localizing 2-medians on probabilistic and deterministic tree networks, Networks, vol. 10, pp. 329–350, 1980.
B. C. Tansel, R. L. Francis and T, J. Lowe, Location of networks: A survey, Management Science, vol. 29, pp. 482–511, 1983.
A. Tarmir, An O(pn 2) algorithm for the p-median and related problems on tree graphs, Operations Research Letters, vol. 19, pp. 59–64, 1996.
B.-F. Wang, S.-C. Ku, and K.-H. Shi, Cost-optimal parallel algorithms for the tree bisector problem and applications, IEEE Transactions on Parallel and Distributed Systems, accepted.
B.-F. Wang, S.-C. Ku, K.-H. Shi, T.-K. Hung, and P.-S. Liu, Parallel algorithms for the tree bisector problem and applications, in Proceedings of the 1999 International Conference on Parallel Processing, pp. 192–199, 1999.
B.-F. Wang, Efficient parallel algorithms for optimally locating a path and a tree of a specified length in a weighted tree network, Journal of Algorithms, Vol. 34, pp. 90–108, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ku, SC., Lu, CJ., Wang, BF., Lin, TC. (2001). Efficient Algorithms for Two Generalized 2-Median Problems on Trees. In: Eades, P., Takaoka, T. (eds) Algorithms and Computation. ISAAC 2001. Lecture Notes in Computer Science, vol 2223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45678-3_65
Download citation
DOI: https://doi.org/10.1007/3-540-45678-3_65
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42985-2
Online ISBN: 978-3-540-45678-0
eBook Packages: Springer Book Archive