Related Experiment Video
Updated: Oct 16, 2025
09:33
A Technical Perspective in Modern Tree-ring Research - How to Overcome Dendroecological and Wood Anatomical Challenges
Published on: March 5, 2015
29.3K
The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees
Qiao Zhang1, Xiucui Guan1, Junhua Jia1
1School of Mathematics, Southeast University, Nanjing, 210096 China.
Journal of Combinatorial Optimization
|October 18, 2021
Summary
This study addresses network interdiction problems to reduce COVID-19 spread by upgrading critical network elements. Researchers developed algorithms to minimize infectious intensity, showing some problems are NP-hard while others are efficiently solvable.
Area of Science:
- Operations Research
- Network Science
- Epidemiology
Background:
- Network interdiction problems are crucial for mitigating infectious diseases like COVID-19.
- Infectious networks can be modeled as rooted trees with edge weights representing infectious intensity.
- Upgrading network edges or nodes (e.g., disinfection, vaccination) reduces infectious spread.
Purpose of the Study:
- To introduce and analyze the Sum of Root-Leaf Distance Interdiction Problem by Upgrading Edges/Nodes on Trees (SDIPT-UE/N).
- To investigate both minimizing infectious intensity under a cost budget (SDIPT-UE/N) and minimizing cost to achieve a target intensity (MCSDIPT-UE/N).
- To develop and evaluate efficient algorithms for various versions of the interdiction problem under different cost norms.
Main Methods:
- Formulating the Sum of Root-Leaf Distance Interdiction Problem by Upgrading Edges/Nodes on Trees (SDIPT-UE/N).
- Proving NP-hardness for SDIPT-UE/N and MCSDIPT-UE/N under weighted Hamming distance by reduction to the 0-1 knapsack problem.
- Developing polynomial-time algorithms for SDIPT-UE/MCSDIPT-UE under weighted L1 norm by transforming to continuous knapsack problems.
- Designing linear-time greedy algorithms for specific cases (unit Hamming distance, unit cost).
- Implementing binary search-based algorithms for minimum cost problems.
Main Results:
- The SDIPT-UE/N and MCSDIPT-UE/N problems are shown to be NP-hard under weighted Hamming distance.
- Efficient O(n) algorithms are provided for SDIPT-UE and MCSDIPT-UE under weighted L1 norm.
- Linear-time greedy algorithms are presented for SDIPT-UE (unit Hamming distance) and SDIPT-UN (unit cost).
- O(n log n) algorithms are developed for MCSDIPT-UE (unit Hamming distance) and MCSDIPT-UN (unit cost) using binary search.
- Numerical experiments demonstrate the performance of the proposed algorithms.
Conclusions:
- The study provides a comprehensive analysis of network interdiction problems for disease control.
- Efficient algorithmic solutions are developed for various problem formulations and cost metrics.
- The findings offer practical tools for public health interventions aimed at reducing infectious disease spread.
Related Concept Videos
01:19Survival Tree
182
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
182
01:12Adjusting a Traverse
166
In the site survey of a four-sided traverse, internal angles are essential to ensure geometric accuracy. The survey revealed that the sum of the measured internal angles was 359 degrees and 48 minutes, which is 12 minutes less than the expected 360 degrees. This discrepancy signals an error likely arising from measurement inaccuracies during the fieldwork.To rectify this error, the adjustment process involved distributing the 12-minute shortfall equally across the four internal angles. By...
166
01:10Interference: Path Lengths
1.5K
Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
1.5K
01:10Design Example: Measuring Distance Between Two Points with Obstructions
163
When measuring distances in areas with physical obstructions, such as a lake in a field, surveyors must employ techniques to calculate accurate lengths without direct line measurements. One effective method is the offset technique, which allows for precise distance estimation over inaccessible stretches.In this scenario, a surveyor must measure a side of an area that crosses a lake. Since the measuring tape cannot span the lake, the surveyor begins by establishing a baseline that aligns with...
163
03:02Primary and Secondary Growth in Roots and Shoots
58.5K
Vascular plants, which account for over 90% of the Earth’s vegetation, all undergo primary growth—which lengthens roots and shoots. Many land plants, notably woody plants, also undergo secondary growth—which thickens roots and shoots.
58.5K
01:15Construction of Root Locus
200
The construction of a root locus involves several key steps to analyze and visualize the behavior of a system's poles with varying gain. The number of branches in the root locus equals the number of closed-loop poles and is symmetrical about the real axis.
For positive gain values, the root locus exists on the real axis to the left of an odd number of finite open-loop poles or zeros. The root locus starts at the open-loop poles and traces the paths of the closed-loop poles as the gain...
For positive gain values, the root locus exists on the real axis to the left of an odd number of finite open-loop poles or zeros. The root locus starts at the open-loop poles and traces the paths of the closed-loop poles as the gain...
200