A derandomized approximation algorithm for the critical node detection problem
From MaRDI portal
Publication:336925
DOI10.1016/j.cor.2013.09.012zbMath1348.90609OpenAlexW2079447226MaRDI QIDQ336925
Mario Ventresca, Dionne M. Aleman
Publication date: 10 November 2016
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2013.09.012
Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (21)
Complexity of the multilevel critical node problem ⋮ Hybrid constructive heuristics for the critical node problem ⋮ An optimal approach for the critical node problem using semidefinite programming ⋮ A genetic algorithm for a class of critical node problems ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ Methods for removing links in a network to minimize the spread of infections ⋮ A novel method of evaluating key nodes in complex networks ⋮ A Region Growing Algorithm for Detecting Critical Nodes ⋮ A Fast Greedy Algorithm for the Critical Node Detection Problem ⋮ The bi-objective critical node detection problem ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ Bound and exact methods for assessing link vulnerability in complex networks ⋮ An integer programming framework for critical elements detection in graphs ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ Literature review: the vaccine supply chain ⋮ An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections ⋮ EIA-CNDP: an exact iterative algorithm for critical node detection problem ⋮ Robust Critical Node Selection by Benders Decomposition ⋮ Relative degree structural hole centrality, \(\mathrm{C}_{\mathrm{RD-SH}}\): a new centrality measure in complex networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of the critical node problem over trees
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Detecting critical nodes in sparse graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- How the science of complex networks can help developing strategies against terrorism
- 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
- The Complexity and Approximability of Minimum Contamination Problems
- Emergence of Scaling in Random Networks
- Cut Problems in Graphs with a Budget Constraint
- Finding k Cuts within Twice the Optimal
- Approximate max-flow min-(multi)cut theorems and their applications
- Collective dynamics of ‘small-world’ networks
- Expander flows, geometric embeddings and graph partitioning
- Expander flows, geometric embeddings and graph partitioning
This page was built for publication: A derandomized approximation algorithm for the critical node detection problem
