A general Evolutionary Framework for different classes of Critical Node Problems. (October 2016)

• Record Type: Journal Article
• Authors: Aringhieri, Roberto; Grosso, Andrea; Hosteins, Pierre; Scatamacchia, Rosario
• Is Part Of: Engineering applications of artificial intelligence. Volume 55(2016:Jul.)
• Page Start: 128
• Page End: 145
• Publication Date: 2016-10
• Subjects: Evolutionary algorithm -- Critical Node Problem -- Graph fragmentation -- Greedy rules -- Connectivity measures; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2016.06.010
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: We design a flexible Evolutionary Framework for solving several classes of the Critical Node Problem (CNP), i.e. the maximal fragmentation of a graph through node deletion, given a measure of connectivity. The algorithm uses greedy rules in order to lead the search towards good quality solutions during reproduction and mutation phases. Such rules, which are only partially reported in the literature, are generalised and adapted to the six different formulations of the CNP considered along the paper. The link between solutions of different CNP formulations is investigated, both quantitatively and qualitatively. Furthermore, we provide a comparison with best known results when those are available in literature that confirms the good overall quality of our solutions.