VNS solutions for the critical node problem

DOI10.1016/J.ENDM.2014.11.006MaRDI QIDQ2631225zbMATH OpenOpenAlexFDO

Authors Roberto Aringhieri, Pierre Hosteins, Rosario Scatamacchia, Andrea Grosso

Publication date 29 July 2016

Full work available at URL https://doi.org/10.1016/j.endm.2014.11.006

zbMATH Keywords

critical node problemgraph fragmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Hybrid constructive heuristics for the critical node problem
• A fast greedy algorithm for the critical node detection problem
• A genetic algorithm for a class of critical node problems
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Variable Neighborhood Search

Cites work

• Complexity of the critical node problem over trees
• Detecting critical nodes in sparse graphs
• Deterministic network interdiction
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Identifying sets of key players in a social network
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• Removing Arcs from a Network
• Variable neighbourhood search: methods and applications
• Variable neighbourhood search: Methods and applications

Cited in

(7)

• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
• The bi-objective critical node detection problem
• The critical node detection problem in networks: a survey
• A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section
• EIA-CNDP: an exact iterative algorithm for critical node detection problem
• Hybrid constructive heuristics for the critical node problem
• A genetic algorithm for a class of critical node problems

This page was built for publication: VNS solutions for the critical node problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631225)