The Reverse Total Weighted Distance Problem on Networks with Variable Edge Lengths

Abstract

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. Additionally, if the cycle has uniform edge lengths, the approach runs in $O(n^3)$ time, where $n$ is the number of vertices in the underlying cycle.