The sum of root-leaf distance interdiction problem with cardinality constraint by upgrading edges on trees

Xiao Li, Xiucui Guan (), Qiao Zhang, Xinyi Yin and Panos M. Pardalos
Additional contact information
Xiao Li: Southeast University
Xiucui Guan: Southeast University
Qiao Zhang: Changzhou University
Xinyi Yin: Southeast University
Panos M. Pardalos: University of Florida

Journal of Combinatorial Optimization, 2024, vol. 48, issue 5, No 3, 30 pages

Abstract: Abstract A network for the transportation of supplies can be described as a rooted tree with a weight of a degree of congestion for each edge. We take the sum of root-leaf distance (SRD) on a rooted tree as the whole degree of congestion of the tree. Hence, we consider the SRD interdiction problem on trees with cardinality constraint by upgrading edges, denoted by (SDIPTC). It aims to maximize the SRD by upgrading the weights of N critical edges such that the total upgrade cost under some measurement is upper-bounded by a given value. The relevant minimum cost problem (MCSDIPTC) aims to minimize the total upgrade cost on the premise that the SRD is lower-bounded by a given value. We develop two different norms including weighted $$l_\infty $$ l ∞ norm and weighted bottleneck Hamming distance to measure the upgrade cost. We propose two binary search algorithms within O( $$n\log n$$ n log n ) time for the problems (SDIPTC) under the two norms, respectively. For problems (MCSDIPTC), we propose two binary search algorithms within O( $$N n^2$$ N n 2 ) and O( $$n \log n$$ n log n ) under weighted $$l_\infty $$ l ∞ norm and weighted bottleneck Hamming distance, respectively. These problems are solved through their subproblems (SDIPT) and (MCSDIPT), in which we ignore the cardinality constraint on the number of upgraded edges. Finally, we design numerical experiments to show the effectiveness of these algorithms.

Keywords: Network interdiction problems; Tree; Greedy algorithm; Binary search method; $$l_\infty $$ l ∞ norm; Bottleneck Hamming distance; 90C27; 90C35 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01230-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:48:y:2024:i:5:d:10.1007_s10878-024-01230-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01230-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().