Complexity of the critical node problem over trees
From MaRDI portal
Publication:547128
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
Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Dynamic programming (90C39)
Related Items
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
