Complexity of the critical node problem over trees

DOI10.1016/j.cor.2011.02.016zbMath1215.90016OpenAlexW2062420311MaRDI QIDQ547128

Marco Di Summa, Andrea Grosso, Marco Locatelli

Publication date: 30 June 2011

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.02.016

zbMATH Keywords

complexitydynamic programmingcritical node problemmulticut in trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Dynamic programming (90C39)

Related Items (37)

Complexity of the multilevel critical node problem ⋮ Hybrid constructive heuristics for the critical node problem ⋮ Minimum cost edge blocker clique problem ⋮ Component-cardinality-constrained critical node problem in graphs ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem ⋮ VNS solutions for the critical node problem ⋮ Minimum edge blocker dominating set problem ⋮ Network interdiction through length-bounded critical disruption paths: a bi-objective approach ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ Improved formulations for minimum connectivity network interdiction problems ⋮ On critical node problems with vulnerable vertices ⋮ Solving the Distance-Based Critical Node Problem ⋮ A Region Growing Algorithm for Detecting Critical Nodes ⋮ A Fast Greedy Algorithm for the Critical Node Detection Problem ⋮ Efficient methods for the distance-based critical node detection problem in complex networks ⋮ The minimum cost network upgrade problem with maximum robustness to multiple node failures ⋮ Exact interdiction models and algorithms for disconnecting networks via node deletions ⋮ The bi-objective critical node detection problem ⋮ The connected critical node problem ⋮ Critical node/edge detection problems on trees ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ The stochastic critical node problem over trees ⋮ On designing networks resilient to clique blockers ⋮ Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem ⋮ EIA-CNDP: an exact iterative algorithm for critical node detection problem ⋮ Robust Critical Node Selection by Benders Decomposition ⋮ Multilevel Approaches for the Critical Node Problem ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs ⋮ The Critical Node Problem Based on Connectivity Index and Properties of Components on Trees ⋮ Selected Topics in Critical Element Detection

Cites Work

• Unnamed Item
• Identifying sets of key players in a social network
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Detecting critical nodes in sparse graphs
• The wireless network jamming problem
• Epidemic dynamics on complex networks

This page was built for publication: Complexity of the critical node problem over trees