Exact interdiction models and algorithms for disconnecting networks via node deletions
From MaRDI portal
Publication:1926497
DOI10.1016/j.disopt.2012.07.001zbMath1254.90280OpenAlexW2120686390MaRDI QIDQ1926497
Siqian Shen, Roshan Goli, J. Cole Smith
Publication date: 28 December 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2012.07.001
Related Items (49)
Complexity of the multilevel critical node problem ⋮ 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 ⋮ A Branch-and-Cut Algorithm for Submodular Interdiction Games ⋮ Minimum edge blocker dominating set problem ⋮ Optimizing dynamic investment decisions for railway systems protection ⋮ A genetic algorithm for a class of critical node problems ⋮ Network interdiction through length-bounded critical disruption paths: a bi-objective approach ⋮ Network interdiction via a critical disruption path: branch-and-price algorithms ⋮ Improved formulations for minimum connectivity network interdiction problems ⋮ Methods for removing links in a network to minimize the spread of infections ⋮ Critical node detection problem for complex network in undirected weighted networks ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Efficient methods for the distance-based critical node detection problem in complex networks ⋮ The minimum cost network upgrade problem with maximum robustness to multiple node failures ⋮ The bi-objective critical node detection problem ⋮ Integer programming methods for solving binary interdiction games ⋮ The connected critical node problem ⋮ Critical node/edge detection problems on trees ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ An integer programming framework for critical elements detection in graphs ⋮ 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 ⋮ An exact method for binary fortification games ⋮ On Bilevel Optimization with Inexact Follower ⋮ A cutting-plane algorithm for solving a weighted influence interdiction problem ⋮ Study of the Matching Interdiction Problem in Some Molecular Graphs of Dendrimers ⋮ Finding Critical Links for Closeness Centrality ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ A compact mixed integer linear formulation for safe set problems ⋮ A simple greedy heuristic for linear assignment interdiction ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ The critical node detection problem in networks: a survey ⋮ On a class of bilevel linear mixed-integer programs in adversarial settings ⋮ An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections ⋮ Optimal detection of critical nodes: improvements to model structure and performance ⋮ Critical nodes in interdependent networks with deterministic and probabilistic cascading failures ⋮ 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 ⋮ Optimal \(K\)-node disruption on a node-capacitated network ⋮ Multilevel Approaches for the Critical Node Problem ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs ⋮ On the Independent Set Interdiction Problem ⋮ The Critical Node Problem Based on Connectivity Index and Properties of Components on Trees ⋮ Political districting to minimize cut edges
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
- Detecting critical nodes in sparse graphs
- Deterministic network interdiction
- Epidemic dynamics on complex networks
- Survivable network design under optimal and heuristic interdiction scenarios
- Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems
- Stochastic Network Interdiction
- OR FORUM—Catching the “Network Science” Bug: Insight and Opportunity for the Operations Researcher
- Design of Survivable Networks: A survey
- Collective dynamics of ‘small-world’ networks
- Node-and edge-deletion NP-complete problems
This page was built for publication: Exact interdiction models and algorithms for disconnecting networks via node deletions