We address the problem of reducing the edge lengths of a network within a given budget so that the sum of weighted distances from each vertex to others is minimized. We call this problem the reverse total weighted distance problem on networks. We first show that the problem is NP-hard by reducing the set cover problem to it in polynomial time. Particularly, we develop a linear time algorithm to solve the problem on a tree. For the problem on cycles, we devise an iterative approach without mentioning the exact complexity. Additionally, if the cycle has uniform edge lengths, we can prove that the specified approach runs in O(n^3) time as each edge of the cycle can be reduced at most once, where n is the number of vertices in the underlying cycle.
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