Algorithm for the problem of minimum total slice location on the graph
,
and
Article Sidebar
Full Text: 
PDF
Abstract
This paper concerns the problem of finding a cut which partitions a connected network into two connected components so that the total weighted distance from any vertices of the network to the cut edge(s) is minimized. This problem is called the minisum cut problem. This paper shows that the problem is NP-hard on general networks by reducing the set cover problem to this problem and the problem on trees can be solved in linear time by dynamic programming.
Tóm tắt
Bài báo này nghiên cứu vấn đề tìm một lát cắt phân chia một đồ thị liên thông thành hai thành phần liên thông rời nhau sao cho tổng khoảng cách có trọng số từ bất kỳ đỉnh nào của đồ thị đến lát cắt là nhỏ nhất. Bài toán này được gọi là bài toán lát cắt tổng tối tiểu. Bài báo sẽ chứng minh rằng bài toán này là NP-khó trên đồ thị tổng quát bằng cách quy giản bài toán phủ tập hợp về bài toán này và đồng thời chỉ ra rằng bài toán trên đồ thị cây có thể giải trong thời gian tuyến tính bằng quy hoạch động.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
Brimberg, J., Juel, H., & Schöbel, A. (2009). Locating a minisum circle in the plane. Discrete Applied Mathematics, 157(5), 901-912. https://doi.org/10.1016/j.dam.2008.03.017
Chen, D., Xia, B., Li, Z., & Huang, J. (2020). Application of P-median method in logistics node location. In IOP Conference Series: Earth and Environmental Science, 526(1). https://doi.org/10.1088/1755-1315/526/1/012175
Garey, M. R., & Johnson, D. S. (1990). Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman
İbrahim Miraç, E., & Eren, Ö. (2020). P-median and maximum coverage models for optimization of distribution plans: A case of United Nations Humanitarian response depots. Smart and Sustainable Supply Chain and Logistics–Trends, Challenges, Methods and Best Practices, (1), 225-246. https://doi.org/10.1007/978-3-030-61947-3_15
Kariv, O., & Hakimi, S. L. (1979a). An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics, 37(3), 513-538. https://doi.org/10.1137/0137040
Kariv, O., & Hakimi, S. L. (1979b). An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37(3), 536-560. https://doi.org/10.1137/0137040
Marianov, V., & Eiselt, H. A. (2024). Fifty Years of Location Theory - A Selective Review. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2024.01.036
Schöbel, A. (1999). Locating lines and hyperplanes: theory and algorithms (Vol. 25). Springer Science & Business Media.