Open AccessThe reverse total weighted distance problem on networks with variable edge lengths
Author(s) -
K. Trung,
Nguyen Hung Thanh
Publication year - 2021
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil2104333n
Subject(s) - vertex cover , mathematics , edge cover , enhanced data rates for gsm evolution , time complexity , cover (algebra) , vertex (graph theory) , combinatorics , set (abstract data type) , steiner tree problem , tree (set theory) , algorithm , mathematical optimization , graph , computer science , mechanical engineering , telecommunications , engineering , programming language
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(n3) time as each edge of the cycle can be reduced at most once, where n is the number of vertices in the underlying cycle.