A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
Tóm tắt
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.
Tài liệu tham khảo
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.