Paper Info
Title
The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees
Abstract
Network interdiction problems by upgading critical edges/nodes have important applications to reduce the infectivity of the COVID-19. A network of confirmed cases can be described as a rooted tree that has a weight of infectious intensity for each edge. Upgrading edges (nodes) can reduce the infectious intensity with contacts by taking prevention measures such as disinfection (treating the confirmed cases, isolating their close contacts or vaccinating the uninfected people). We take the sum of root-leaf distance on a rooted tree as the whole infectious intensity of the tree. Hence, we consider the sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees (SDIPT-UE/N). The problem (SDIPT-UE) aims to minimize the sum of root-leaf distance by reducing the weights of some critical edges such that the upgrade cost under some measurement is upper-bounded by a given value. Different from the problem (SDIPT-UE), the problem (SDIPT-UN) aims to upgrade a set of critical nodes to reduce the weights of the edges adjacent to the nodes. The relevant minimum cost problem (MCSDIPT-UE/N) aims to minimize the upgrade cost on the premise that the sum of root-leaf distance is upper-bounded by a given value. We develop different norms to measure the upgrade cost. Under weighted Hamming distance, we show the problems (SDIPT-UE/N) and (MCSDIPT-UE/N) are NP-hard by showing the equivalence of the two problems and the 0–1 knapsack problem. Under weighted $$l_1$$ norm, we solve the problems (SDIPT-UE) and (MCSDIPT-UE) in O(n) time by transforimg them into continuous knapsack problems. We propose two linear time greedy algorithms to solve the problem (SDIPT-UE) under unit Hamming distance and the problem (SDIPT-UN) with unit cost, respectively. Furthermore, for the the minimum cost problem (MCSDIPT-UE) under unit Hamming distance and the problem (MCSDIPT-UN) with unit cost, we provide two $$O(n\log n)$$ time algorithms by the binary search methods. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.
Year
DOI
Venue
2022
10.1007/s10878-021-00819-w
Journal of Combinatorial Optimization
Keywords
DocType
Volume
Network interdiction problem, Upgrading critical edges, Upgrading critical nodes, Tree, Knapsack problem, Greedy algorithm
Journal
44
Issue
ISSN
Citations 
1
1382-6905
0
PageRank 
References 
Authors
0.34
6
4
Name
Order
Citations
PageRank
Qiao Zhang122.43
Xiucui Guan2325.85
Junhua Jia300.34
Xinqiang Qian400.34