• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Maximum shortest path interdiction problem by upgrading edges on trees under hamming distance

Optimization Letters. 2021. Vol. 15. P. 2661-2680.
Zhang Q., Guan X., Wang H., Pardalos P. M.

We consider the maximum shortest path interdiction problem by upgrading edges on
trees under Hamming distance (denoted by (MSPITH)), which has wide applications
in transportation network, networkwar and terrorist network. The problem (MSPITH)
aims to maximize the length of the shortest path from the root of a tree to all its leaves
by upgrading edge weights such that the upgrade cost under sum-Hamming distance
is upper-bounded by a given value. We show that the problem (MSPITH) under
weighted sum-Hamming distance is NP-hard. We consider two cases of the problem
(MSPITH) under unit sum-Hamming distance based on the number K of critical
edges. We propose a greedy algorithm within O(n + l log l) time when K = 1 and a
dynamic programming algorithm within O(n(log n + K3)) time when K > 1, where
n and l are the numbers of nodes and leaves in a tree, respectively. Furthermore, we
consider a minimum cost shortest path interdiction problem by upgrading edges on
trees under unit Hamming distance, denoted by (MCSPITUH) and propose a binary
search algorithm within O(n4 log n) time, where a dynamic programming algorithm
is executed in each iteration to solve its corresponding problem (MSPITH). Finally,
we design numerical experiments to show the effectiveness of the algorithms.