“The critical node/edge detection problem on trees”
Wednesday 15 December 2021 h. 14:30 16:00 - Room 2AB45 and Zoom - Syed Md Omar Faruk (Padova, Dip. Mat.)
Abstract
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.
The video of the seminar will appear shortly afterwards in this Mediaspace channel.
