Abstract
The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos/neg-weighted’ problem defined on a cactus. The algorithm visits every vertex just once and runs thus in linear time.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Auletta, V., Parente, D., Persiano, G.: Dynamic and static algorithms for optimal placement of resources in a tree. Theor. Comput. Sci.165, 441–461 (1996).
Bern, M. W., Lawler, E. L., Wong, A.: Linear-time computation of optimal subgraphs of decomposable graphs. J. Algorithms8, 216–235 (1987).
Chen, M.-L., Francis, R. L., Lawrence, J. F., Lowe, T. J., Tufekci, S.: Block-vertex duality and the one-median problem. Networks15, 395–412 (1985).
Courant, R., Robbins, H.: What is Mathematics? Oxford: Oxford University Press 1941.
Goldman, A. J.: Optimal center location in simple networks. Transport. Sci.5, 212–221 (1971).
Hakimi, S. L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res.12, 450–459 (1964).
Hua, L. K., et al.: Applications of mathematical models to wheat harvesting. Chin. Math.2, 77–91 (1962).
Kariv, O., Hakimi, S. L.: An algorithmic approach to network location problems, Part 2: Thep-median. SIAM J. Appl. Math.37, 539–560 (1979).
Krarup, J.: On ‘A Complementary Problem; of Courant and Robbins, Report 96/39, DIKU (Dept. of Computer Science, University of Copenhagen). To appear in Location Theory.
Author information
Authors and Affiliations
Additional information
This research has been supported by the Spezialforschungsbereich F 003 ‘Optimierung und Kontrolle’, Projektbereich Diskrete Optimierung.
Rights and permissions
About this article
Cite this article
Burkard, R.E., Krarup, J. A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing 60, 193–215 (1998). https://doi.org/10.1007/BF02684332
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02684332