Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
From MaRDI portal
Publication:4648696
DOI10.1002/net.20464zbMath1251.90376OpenAlexW1988680180MaRDI QIDQ4648696
Publication date: 15 November 2012
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.20464
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (33)
Interdicting facilities in tree networks ⋮ 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 ⋮ 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 ⋮ A mixed-integer programming approach for locating jamming devices in a flow-jamming attack ⋮ Improved formulations for minimum connectivity network interdiction problems ⋮ Critical node detection problem for complex network in undirected weighted networks ⋮ Efficient methods for the distance-based critical node detection problem in complex networks ⋮ 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 ⋮ Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ 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 ⋮ Finding Critical Links for Closeness Centrality ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ The critical node detection problem in networks: a survey ⋮ Optimal detection of critical nodes: improvements to model structure and performance ⋮ EIA-CNDP: an exact iterative algorithm for critical node detection problem ⋮ Sequential Shortest Path Interdiction with Incomplete Information ⋮ 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
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Identifying sets of key players in a social network
- Complexity of the critical node problem over trees
- Sparsest cuts and bottlenecks in graphs
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
- Sparsest cuts and concurrent flows in product graphs.
- Deterministic network interdiction
- A cutting plane algorithm for computing \(k\)-edge survivability of a network
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Epidemic dynamics on complex networks
- On the hardness of approximating Multicut and Sparsest-Cut
- Survivable network design under optimal and heuristic interdiction scenarios
- Stochastic Network Interdiction
- $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
- Euclidean distortion and the sparsest cut
- A Best Possible Heuristic for the k-Center Problem
- The Recognition of Series Parallel Digraphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- Handbook of Graph Theory
- Random graph models of social networks
- Design of Survivable Networks: A survey
- Collective dynamics of ‘small-world’ networks
- Removing Arcs from a Network
This page was built for publication: Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
