Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
From MaRDI portal
Publication:4648696
Recommendations
- The critical node problem based on connectivity index and properties of components on trees
- Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- Critical node/edge detection problems on trees
- Exact interdiction models and algorithms for disconnecting networks via node deletions
Cites work
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- A Best Possible Heuristic for the k-Center Problem
- A cutting plane algorithm for computing \(k\)-edge survivability of a network
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- An O( n)-approximation algorithm for directed sparsest cut
- Collective dynamics of `small-world' networks
- Complexity of the critical node problem over trees
- Design of Survivable Networks: A survey
- Detecting critical nodes in sparse graphs
- Deterministic network interdiction
- Epidemic dynamics on complex networks
- Euclidean distortion and the sparsest cut (extended abstract)
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Handbook of Graph Theory
- scientific article; zbMATH DE number 49666 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 5070513 (Why is no real title available?)
- Identifying sets of key players in a social network
- Linear-time computability of combinatorial problems on series-parallel graphs
- Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure
- Network flows. Theory, algorithms, and applications.
- On the hardness of approximating Multicut and Sparsest-Cut
- Random graph models of social networks
- Removing Arcs from a Network
- Sparsest cuts and bottlenecks in graphs
- Sparsest cuts and concurrent flows in product graphs.
- Stochastic network interdiction
- Survivable network design under optimal and heuristic interdiction scenarios
- The Recognition of Series Parallel Digraphs
Cited in
(39)- Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
- A mixed-integer programming approach for locating jamming devices in a flow-jamming attack
- Improved formulations for minimum connectivity network interdiction problems
- The critical node detection problem in networks: a survey
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Optimal detection of critical nodes: improvements to model structure and performance
- EIA-CNDP: an exact iterative algorithm for critical node detection problem
- Interdicting facilities in tree networks
- Critical node detection problem for complex network in undirected weighted networks
- 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
- Exact identification of critical nodes in sparse networks via new compact formulations
- 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
- Component-cardinality-constrained critical node problem in graphs
- Analysis of complex network performance and heuristic node removal strategies
- Minimum edge blocker dominating set problem
- A genetic algorithm for a class of critical node problems
- Bound and exact methods for assessing link vulnerability in complex networks
- An integer programming framework for critical elements detection in graphs
- Detecting critical node structures on graphs: a mathematical programming approach
- Sequential Shortest Path Interdiction with Incomplete Information
- Multilevel approaches for the critical node problem
- The critical node problem based on connectivity index and properties of components on trees
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Finding critical links for closeness centrality
- 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
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- A survey on mixed-integer programming techniques in bilevel optimization
- The critical node game
- Destroying densest subgraphs is hard
- The k-way vertex cut problem on bipartite graphs: complexity results and algorithms
- Destroying densest subgraphs is hard
This page was built for publication: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4648696)
