Hybrid constructive heuristics for the critical node problem

DOI10.1007/S10479-016-2110-YzbMath1334.90185OpenAlexW2273546298MaRDI QIDQ271993

Bernardetta Addis, Andrea Grosso, Roberto Aringhieri, Pierre Hosteins

Publication date: 20 April 2016

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-016-2110-y

zbMATH Keywords

critical node problemgraph fragmentationhybrid heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (14)

Complexity of the multilevel critical node problem ⋮ Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem ⋮ A genetic algorithm for a class of critical node problems ⋮ Critical node detection problem for complex network in undirected weighted networks ⋮ Solving the Distance-Based Critical Node Problem ⋮ Efficient methods for the distance-based critical node detection problem in complex networks ⋮ The bi-objective critical node detection problem ⋮ The connected critical node problem ⋮ Critical node/edge detection problems on trees ⋮ A fast tri-individual memetic search approach for the distance-based critical node problem ⋮ Efficient heuristic algorithm for identifying critical nodes in planar networks ⋮ A preliminary analysis of the distance based critical node problem ⋮ The critical node detection problem in networks: a survey ⋮ EIA-CNDP: an exact iterative algorithm for critical node detection problem

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Identifying sets of key players in a social network
• A derandomized approximation algorithm for the critical node detection problem
• An integer programming framework for critical elements detection in graphs
• Complexity of the critical node problem over trees
• Detecting critical nodes in sparse graphs
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Deterministic network interdiction
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Exact identification of critical nodes in sparse networks via new compact formulations
• VNS solutions for the critical node problem
• A faster algorithm for betweenness centrality*
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Selected Topics in Critical Element Detection
• Removing Arcs from a Network
• Benchmarking optimization software with performance profiles.

This page was built for publication: Hybrid constructive heuristics for the critical node problem