Minimum-Cost Shortest-Path Interdiction Problem Involving Upgrading Edges on Trees with Weighted l ∞ Norm

Qiao Zhang and Xiao Li ()
Additional contact information
Qiao Zhang: Aliyun School of Big Data, Changzhou University, Changzhou 213164, China
Xiao Li: School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA

Mathematics, 2025, vol. 13, issue 19, 1-19

Abstract: Network interdiction problems involving edge deletion on shortest paths have wide applications. However, in many practical scenarios, the complete removal of edges is infeasible. The minimum-cost shortest-path interdiction problem for trees with the weighted l ∞ norm (MCSPIT ∞ ) is studied in this paper. The goal is to upgrade selected edges at minimum total cost such that the shortest root–leaf distance is bounded below by a given value. We designed an O ( n log n ) algorithm based on greedy techniques combined with a binary search method to solve this problem efficiently. We then extended the framework to the minimum-cost shortest-path double interdiction problem for trees with the weighted l ∞ norm, which imposes an additional requirement that the sum of root–leaf distances exceed a given threshold. Building upon the solution to (MCSPIT ∞ ), we developed an equally efficient O ( n log n ) algorithm for this variant. Finally, numerical experiments are presented to demonstrate both the effectiveness and practical performance of the proposed algorithms.

Keywords: network interdiction problem; double interdiction problem; upgrading edges; shortest path; tree; weighted l∞ norm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/19/3219/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/19/3219/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:19:p:3219-:d:1766258

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().