The Critical Node Problem Based On Combination Of The Connectivity Index And Degrees In The Residual Graph

In this paper,we consider the critical node problems in an undirected graph,in which some nodes are deleted in a given undirected graph G to make the maximum fragmentation of the residual graph in some certain sense.We give a new criterion about the fragmentation,in which both the connectivity index and the degree of the residual graph are considered.We try to optimize the relationship between the connectivity index and the degree of the residual graph,so that unconnectedness increases in the residual graph,and then results in better fragmentation.In the first chapter,we introduce the background knowledge of the critical nodes,as well as the general research on some criterions describing the fragmentation.We also list some preliminary knowledge.In the second chapter,we study the dynamic programming method which is considered based on the relationship between the connectivity index and degree in the residual graph on the tree.We derive the recursion formula.We analyze the time complexity of O(n3K2),followed with some numerical test of the algorithm.In the third chapter,we consider the relationship among the three factors:the connectivity index,sum of degree and max of the degree in the residual graph.In this part,we also consider the cost cij edges by deleting critical nodes,as well as the weight wi of deleting nodes.We first consider the problem on trees,then generalize it to the general graph.In both of these two types of graphs,we consider six kinds of values of wi and cij,including(0,1),(0,>1),(1,0),(?1,0),(1,1),(? 1,? 1).In any case,we develop a greedy type algorithm to find the critical nodes based on different combination coefficients of three factors.We present numerical simulations for the critical node problem under all these cases.In the last chapter,we make a summary and propose the relevant research work in the future.