Plenary Talks

We study two problems that involve in detecting critical nodes in networks. In the first problem, we seek a set of vertices with a specified cardinality whose deletion results in maximum number of disconnected components. In an alternate version of the problem, we desire the specified amount of disconnectivity and try to minimize the number of vertices to be deleted in order to achieve this. This is referred to as the critical node detection problem, and finds applications in supply chain networks, epidemic control and identification of influential individuals in social networks, and telecommunication networks. In a supply chain network, it is important to ensure connectivity between supply and demand nodes. These nodes could be secured or made more resilient in order to retain connectivity in the network. In this talk, we review the recent work in this area and provide formulations based on integer linear programming. We also discuss new complexity results and present heuristic techniques to solve the problems.