In location theory, group median generalizes the concepts of both median and center. We address in this paper the problem of modifying vertex weights of a tree at minimum total cost so that a prespecified vertex becomes a group 1-median with respect to the new weights. We call this problem the inverse group 1-median on trees. To solve the problem, we first reformulate the optimality criterion for a vertex being a group 1-median of the tree. Based on this result, we prove that the problem is NP-hard. Particularly, the corresponding problem with exactly two groups is however solvable in O(n^2log n) time, where n is the number of vertices in the tree.
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