Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth

DOI10.1016/j.dam.2013.03.021zbMath1285.05042OpenAlexW2054950944MaRDI QIDQ2444525

Bernardetta Addis, Marco Di Summa, Andrea Grosso

Publication date: 10 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.03.021

zbMATH Keywords

complexitydynamic programmingtreewidthcritical node problem

Mathematics Subject Classification ID

Dynamic programming (90C39) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Complexity of the multilevel critical node problem, Hybrid constructive heuristics for the critical node problem, Component-cardinality-constrained critical node problem in graphs, 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 via a critical disruption path: branch-and-price algorithms, A derandomized approximation algorithm for the critical node detection problem, 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, Critical node detection problem for complex network in undirected weighted networks, On critical node problems with vulnerable vertices, Integer Programming Formulations for Minimum Spanning Tree Interdiction, 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 bi-objective critical node detection problem, The connected critical node problem, Critical node/edge detection problems on trees, The firebreak problem, Bound and exact methods for assessing link vulnerability in complex networks, An integer programming framework for critical elements detection in graphs, The stochastic critical node problem over trees, Min–max optimization of node‐targeted attacks in service networks, Influential node detection of social networks based on network invulnerability, Detecting critical node structures on graphs: A mathematical programming approach, On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon, The critical node detection problem in networks: a survey, Parameterized complexity of critical node cuts, An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections, 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

Cites Work

• Unnamed Item
• Identifying sets of key players in a social network
• Complexity of the critical node problem over trees
• Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
• Detecting critical nodes in sparse graphs
• Some simplified NP-complete graph problems
• Treewidth. Computations and approximations
• The maximum edge biclique problem is NP-complete
• Deterministic network interdiction
• A cutting plane algorithm for computing \(k\)-edge survivability of a network
• Epidemic dynamics on complex networks
• Cardinality-Constrained Critical Node Detection Problem
• How to Cut a Graph into Many Pieces
• Complexity of Finding Embeddings in a k-Tree
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Disconnecting graphs by removing vertices: a polyhedral approach
• Removing Arcs from a Network
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth