This paper addresses the problem of modifying the vertex weights of a block graph at minimum total cost so that a prespecified vertex becomes a 1-median of the perturbed graph. We call this problem the inverse 1-median problem on block graphs with variable vertex weights. For block graphs with equal edge lengths in each block, we can formulate the problem as a univariate optimization problem. By the convexity of the objective function, the local optimizer is also the global one. Therefore, we use the convexity to develop an O(M log M) algorithm that solves the problem on block graphs with M vertices.
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