We address the problem of modifying vertex weights of a block graph at minimum total cost so that a predetermined set of p connected vertices becomes a connected p-median on the perturbed block graph. This problem is the so-called inverse connected p-median problem on block graphs. We consider the problem on a block graph with uniform edge lengths under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. To solve the problem, we first find an optimality criterion for a set that is a connected p-median. Based on this criterion, we can formulate the problem as a convex or quasiconvex univariate optimization problem. Finally, we develop combinatorial algorithms that solve the problems under the three cost functions in O(nlog n) time, where n is the number of vertices in the underlying block graph.
Tạp chí khoa học Trường Đại học Cần Thơ
Lầu 4, Nhà Điều Hành, Khu II, đường 3/2, P. Xuân Khánh, Q. Ninh Kiều, TP. Cần Thơ
Điện thoại: (0292) 3 872 157; Email: tapchidhct@ctu.edu.vn
Chương trình chạy tốt nhất trên trình duyệt IE 9+ & FF 16+, độ phân giải màn hình 1024x768 trở lên