Geodesic
The reverse total weighted distance problem on networks with variable edge lengths
Filomat, Tome 35 (2021) no. 4, p. 1333

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

DOI

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
DOI : 10.2298/FIL2104333N
Classification : 90B10, 90B80, 90C27
Keywords: Combinatorial optimization - Reverse optimization - Complexity - Tree - Cycle 
Kien Trung Nguyen; Nguyen Thanh Hung. The reverse total weighted distance problem on networks with variable edge lengths. Filomat, Tome 35 (2021) no. 4, p. 1333 . doi: 10.2298/FIL2104333N
@article{10_2298_FIL2104333N,
     author = {Kien Trung Nguyen and Nguyen Thanh Hung},
     title = {The reverse total weighted distance problem on networks with variable edge lengths},
     journal = {Filomat},
     pages = {1333 },
     year = {2021},
     volume = {35},
     number = {4},
     doi = {10.2298/FIL2104333N},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/FIL2104333N/}
}
TY  - JOUR
AU  - Kien Trung Nguyen
AU  - Nguyen Thanh Hung
TI  - The reverse total weighted distance problem on networks with variable edge lengths
JO  - Filomat
PY  - 2021
SP  - 1333 
VL  - 35
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.2298/FIL2104333N/
DO  - 10.2298/FIL2104333N
LA  - en
ID  - 10_2298_FIL2104333N
ER  - 
%0 Journal Article
%A Kien Trung Nguyen
%A Nguyen Thanh Hung
%T The reverse total weighted distance problem on networks with variable edge lengths
%J Filomat
%D 2021
%P 1333 
%V 35
%N 4
%U http://geodesic.mathdoc.fr/articles/10.2298/FIL2104333N/
%R 10.2298/FIL2104333N
%G en
%F 10_2298_FIL2104333N

Cité par Sources :