Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
From MaRDI portal
Publication:2444525
Recommendations
- Complexity of the critical node problem over trees
- Critical node/edge detection problems on trees
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- The critical node problem based on connectivity index and properties of components on trees
- scientific article; zbMATH DE number 4060712
Cites work
- A cutting plane algorithm for computing \(k\)-edge survivability of a network
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Cardinality-Constrained Critical Node Detection Problem
- Complexity of Finding Embeddings in a k-Tree
- Complexity of the critical node problem over trees
- Detecting critical nodes in sparse graphs
- Deterministic network interdiction
- Disconnecting graphs by removing vertices: a polyhedral approach
- Epidemic dynamics on complex networks
- How to Cut a Graph into Many Pieces
- scientific article; zbMATH DE number 4121424 (Why is no real title available?)
- Identifying sets of key players in a social network
- Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- Removing Arcs from a Network
- Some simplified NP-complete graph problems
- The maximum edge biclique problem is NP-complete
- Treewidth. Computations and approximations
Cited in
(56)- Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- The bi-objective critical node detection problem
- Critical node cut parameterized by treewidth and solution size is \(W[1]\)-hard
- 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
- Cut-threshold graphs
- 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
- Hybrid constructive heuristics for the 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
- Component-cardinality-constrained critical node problem in graphs
- Complexity of most vital nodes for independent set in graphs related to tree structures
- 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
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Bound and exact methods for assessing link vulnerability in complex networks
- An integer programming framework for critical elements detection in graphs
- The most vital nodes with respect to independent set and vertex cover
- Computing Critical Nodes in Directed Graphs
- 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
- Multilevel approaches for the critical node problem
- On finding optimal polytrees
- 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
- Parameterized complexity of critical node cuts
- Parameterized complexity of critical node cuts
- scientific article; zbMATH DE number 7059791 (Why is no real title available?)
- Complexity of the critical node problem over trees
- 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
- On critical node problems with vulnerable vertices
- The critical node game
- Valid inequalities for the -edge disruptor problem
- Preprocessing and valid inequalities for exact detection of critical nodes via integer programming
- The k-way vertex cut problem on bipartite graphs: complexity results and algorithms
- An FPTAS for connectivity interdiction
- An FPTAS for connectivity interdiction
This page was built for publication: Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444525)
