Geodesic
Efficient Algorithms for the Reverse Shortest Path Problem on Trees Under the Hamming Distance
Yugoslav journal of operations research, Tome 27 (2017) no. 1, p. 46 .

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

Given a network G(V; A; c) and a collection of origin-destination pairs with prescribed values, the reverse shortest path problem is to modify the arc length vector c as little as possible under some bound constraints such that the shortest distance between each origin-destination pair is upper bounded by the corresponding prescribed value. It is known that the reverse shortest path problem is NP-hard even on trees when the arc length modifications are measured by the weighted sum-type Hamming distance. In this paper, we consider two special cases of this problem which are polynomially solvable. The first is the case with uniform lengths. It is shown that this case transforms to a minimum cost flow problem on an auxiliary network. An efficient algorithm is also proposed for solving this case under the unit sum-type Hamming distance. The second case considered is the problem without bound constraints. It is shown that this case is reduced to a minimum cut problem on a tree-like network. Therefore, both cases studied can be solved in strongly polynomial time.
Classification : 90C27, 90C35, 05C85
Keywords: Inverse problems, Shortest path problem, Hamming distance, Combinatorial algorithms 
@article{YJOR_2017_27_1_a2,
     author = {Javad Tayyebi and Massoud Aman},
     title = {Efficient {Algorithms} for the {Reverse} {Shortest} {Path} {Problem} on {Trees} {Under} the {Hamming} {Distance}},
     journal = {Yugoslav journal of operations research},
     pages = {46 },
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2017_27_1_a2/}
}
TY  - JOUR
AU  - Javad Tayyebi
AU  - Massoud Aman
TI  - Efficient Algorithms for the Reverse Shortest Path Problem on Trees Under the Hamming Distance
JO  - Yugoslav journal of operations research
PY  - 2017
SP  - 46 
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2017_27_1_a2/
LA  - en
ID  - YJOR_2017_27_1_a2
ER  - 
%0 Journal Article
%A Javad Tayyebi
%A Massoud Aman
%T Efficient Algorithms for the Reverse Shortest Path Problem on Trees Under the Hamming Distance
%J Yugoslav journal of operations research
%D 2017
%P 46 
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2017_27_1_a2/
%G en
%F YJOR_2017_27_1_a2
Javad Tayyebi; Massoud Aman. Efficient Algorithms for the Reverse Shortest Path Problem on Trees Under the Hamming Distance. Yugoslav journal of operations research, Tome 27 (2017) no. 1, p. 46 . http://geodesic.mathdoc.fr/item/YJOR_2017_27_1_a2/