EIACNDP
swMATH ID:  38601 
Software Authors:  Rezaei, Javad; ZareMirakabad, Fatemeh; MirHassani, Seyed Ali; Marashi, SayedAmir 
Description:  EIACNDP: an exact iterative algorithm for critical node detection problem. In designing reliable and impermeable networks, the robustness of the network is evaluated against the removal and failure of the node or edge where the network robustness (network connectivity) is measured using various metrics (objective functions) such as the number of connected components, size of the largest connected component, and pairwise connectivity. Critical node detection problem (CNDP) is one of the main issues in this literature, which aims to find a set of vertices whose removal maximizes or minimizes some objective function. In this paper, the focus is on solving CNDP, considering the size of the largest connected component as its objective function. In this regard, we introduce a new problem called KGroupDivisionProblem and present a mixed integer linear programming model to solve it. We prove that under certain circumstances, any optimal solution of the new problem is also an optimal solution of CNDP. Analyzing the performance of the proposed model on solving CNDP, indicates that this model is highly competitive against the base model in the literature. Furthermore, a novel exact algorithm is introduced which improves the proposed mixed integer linear programming model to address CNDP more efficiently. The results show that the proposed algorithm is much more efficient, and, compared with the base model, it can solve the problem on networks with a higher number of nodes. 
Homepage:  https://www.sciencedirect.com/science/article/abs/pii/S0305054820302550 
Keywords:  exact algorithm; critical node; largest connected component; mixed integer linear programming; network vulnerability 
Related Software:  SparseMatrix 
Referenced in:  2 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

EIACNDP: an exact iterative algorithm for critical node detection problem. Zbl 07350533 Rezaei, Javad; ZareMirakabad, Fatemeh; MirHassani, Seyed Ali; Marashi, SayedAmir 
2021

all
top 5
Referenced by 7 Authors
1  Carvalho, Margarida 
1  Hosteins, Pierre 
1  Marashi, SayedAmir 
1  Mirhassani, Seyed Ali 
1  Nabli, Adel 
1  Rezaei, Javad 
1  ZareMirakabad, Fatemeh 
Referenced in 2 Serials
1  Journal of Computer and System Sciences 
1  Computers & Operations Research 
Referenced in 3 Fields
1  Computer science (68XX) 
1  Operations research, mathematical programming (90XX) 
1  Game theory, economics, finance, and other social and behavioral sciences (91XX) 