Bài toán vị trí liên thông không mong muốn trên cây
Abstract
In this paper, the connected p-maxian problem on tree graphs is considered. To solve the problem, firstly, a finite dominating is found. Then, a combinatorial algorithm is developped for the problem based on computing objective values with respect to all elements in the dominating set.
Tóm tắt
Trong bài báo này, bài toán liên thông p-maxian trên đồ thị cây sẽ được xem xét. Để giải bài toán, đầu tiên, một tập trội hữu hạn được tìm ra. Sau đó, một thuật toán tổ hợp được phát triển cho bài toán dựa trên việc tính toán giá trị mục tiêu đối với mỗi phần tử trong tập trội.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Tài liệu tham khảo
Bai, C., Kang, L., & Shan, E. (2018). The connected p-center problem on cactus graphs. Theoretical Computer Science, 749, 59-65. https://doi.org/10.1016/j.tcs.2017.09.028
Burkard, R. E., Fathali, J., & Kakhki, H. T. (2007). The p-maxian problem on a tree. Operations Research Letters, 35, 331-335. https://doi.org/10.1016/j.orl.2006.03.016
Chang, S. C., Yen, W. C. K., Wang, Y. L., & Liu, J. J. (2016). The connected p-median problem on block graphs. Optimization Letters, 10, 1191-1201. https://doi.org/10.1007/s11590-015-0912-5
Cheng, Y., & Kang, L. (2010). The p-maxian problem on interval graphs. Discrete Applied Mathematics, 158, 1986-1993. https://doi.org/10.1016/j.dam.2010.08.021
Church, R. L., & Garfinkel, R. S. (1978). Locating an obnoxious facility on a network. Transportation Science, 12, 107-118. https://doi.org/10.1287/trsc.12.2.107
Drezner, Z., & Hamacher, H. W. (2002). Facility location - Applications and Theory. Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-642-56082-8
Kang, L., & Cheng, Y. (2010). The p-maxian problem on block graphs. Journal of Combinatorial Optimization, 20, 131-141. https://doi.org/10.1007/s10878-008-9198-1
Kang, L., Bai, C., Shan, E., & Nguyen, K. (2014). The 2-maxian problem on cactus graphs. Discrete Optimization, 13,16-22. https://doi.org/10.1016/j.disopt.2014.04.001
Kang, L., Zhou, L., & Shan, E. (2018). Algorithms for connected p-centdian problem on block graphs. Journal of Combinatorial Optimization, 36, 252-263.
https://doi.org/10.1007/s10878-016-0058-0
Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics, 37, 513-538. https://doi.org/10.1137/0137040
Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics, 37, 539-560. https://doi.org/10.1137/0137041
Nguyen, K. T., Hung, N. T., & Huong, N. T. (2020). A linear time algorithm for the p-maxian problem on trees with distance constraint. Journal of Combinatorial Optimization, 40, 1030-1043.
https://doi.org/10.1007/s10878-020-00650-9
Tamir, A. (1991). Obnoxious facility location on graphs. SIAM Journal on Discrete Mathematics, 4, 550-567. https://doi.org/10.1137/0404048
Ting, S. S. (1984). A linear-time algorithm for maximum facility location on tree networks. Transportation Science, 18, 76-84. https://doi.org/10.1287/trsc.18.1.76
Yen, W. C. K. (2012). The connected p-center problem on block graphs with forbidden vertices. Theoretical Computer Science, 47, 13-24. https://doi.org/10.1016/j.tcs.2011.12.013