The connected critical node problem
From MaRDI portal
Publication:2672625
DOI10.1016/j.tcs.2022.05.011OpenAlexW4280619407MaRDI QIDQ2672625
Rosario Scatamacchia, Pierre Hosteins, Roberto Aringhieri, Andrea Grosso
Publication date: 13 June 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.05.011
complexitydynamic programmingtreewidthtreesseries-parallel graphscritical node problemK-way vertex cut problem
Cites Work
- Unnamed Item
- Identifying sets of key players in a social network
- Hybrid constructive heuristics for the critical node problem
- Component-cardinality-constrained critical node problem in graphs
- Safe set problem on graphs
- Network interdiction via a critical disruption path: branch-and-price algorithms
- An integer programming framework for critical elements detection in graphs
- Complexity of the critical node problem over trees
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- Treewidth. Computations and approximations
- Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
- The critical node detection problem in networks: a survey
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- Deterministic network interdiction
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- On the approximability of positive influence dominating set in social networks
- An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- Epidemic dynamics on complex networks
- Cardinality-Constrained Critical Node Detection Problem
- Complexity of Finding Embeddings in a k-Tree
- The Recognition of Series Parallel Digraphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
- Complexity and approximability of the k‐way vertex cut
- Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
- On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
- Safe sets, network majority on weighted trees
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: The connected critical node problem
