Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
From MaRDI portal
Publication:2444525
DOI10.1016/j.dam.2013.03.021zbMath1285.05042MaRDI 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
90C39: Dynamic programming
05C12: Distance in graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Related Items
Detecting critical node structures on graphs: A mathematical programming approach, Multilevel Approaches for the Critical Node Problem, The Critical Node Problem Based on Connectivity Index and Properties of Components on Trees, Integer Programming Formulations for Minimum Spanning Tree Interdiction, Solving the Distance-Based Critical Node Problem, Critical node/edge detection problems on trees, The firebreak problem, The stochastic critical node problem over trees, Min–max optimization of node‐targeted attacks in service networks, Hybrid constructive heuristics for the critical node problem, Component-cardinality-constrained critical node problem in graphs, 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, Bound and exact methods for assessing link vulnerability in complex networks, An integer programming framework for critical elements detection in graphs, Parameterized complexity of critical node cuts, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, The bi-objective critical node detection problem, The critical node detection problem in networks: a survey, 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, Complexity of the multilevel critical node problem, Critical node detection problem for complex network in undirected weighted networks, On critical node problems with vulnerable vertices, Influential node detection of social networks based on network invulnerability, On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon, A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs, VNS solutions for the critical node problem, Efficient methods for the distance-based critical node detection problem in complex networks, The connected critical node problem, Robust Critical Node Selection by Benders Decomposition, A Region Growing Algorithm for Detecting Critical Nodes, A Fast Greedy Algorithm for the Critical Node Detection Problem
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
