Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs

DOI10.1002/net.20464zbMath1251.90376MaRDI QIDQ4648696

Siqian Shen, J. Cole Smith

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

zbMATH Keywords

tree; dynamic programming; polynomial-time algorithm; series-parallel graph; critical node problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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, Critical node/edge detection problems on trees, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, A survey on mixed-integer programming techniques in bilevel optimization, Hybrid constructive heuristics for the critical node problem, 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, 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, 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, Robust Critical Node Selection by Benders Decomposition

Uses Software

• LAPACK

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