THE CRITICAL NODE/EDGE DETECTION PROBLEM ON TREES
Critical node or edge detection problems are a family of optimization problems defined on graphs, where one is required to remove a limited number of nodes and/or edges in order to minimize some measure of the connectivity of the residual graph. Problems of this type are important from a practical point of view because of their relevance in a number of practical applications.
We start this seminar by giving the definitions of the critical node/edge detection problem (CNDP/CEDP) and some connectivity metrics with an example. After that, we present a dynamic programming approach for solving the CNDP on trees when the node weights are all equal to one and all connections between pairs of nodes have unit cost. Then, we will move to consider the CEDP on trees and similarly deal with the case with unit costs and unit edge weights. Finally, we will present dynamic programming algorithms for the “mixed” case, in which nodes and edges can be simultaneously removed from the graph.
- Tags
-