Phan Minh Tâm * , Nguyễn Đặng Ngọc Ngân Nguyễn Hoàng Duy

* Tác giả liên hệ (tamb2106958@student.ctu.edu.vn)

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.

Keywords: Location problem, p-maxian, 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.

Từ khóa: Bài toán vị trí, p-maxian, tập trội

Article Details

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