Network interdiction via a critical disruption path: branch-and-price algorithms

DOI10.1016/J.COR.2013.04.016MaRDI QIDQ336604zbMATHOpenAlexFDO

Authors Donatella Granata, Gregory Steeger, Steffen Rebennack

Publication date 10 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2013.04.016

zbMATH Keywords

NP-completenessbranch-and-pricemixed-integer linear programmingnetwork interdictioncuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Mixed integer programming (90C11)

Recommendations

• Network interdiction through length-bounded critical disruption paths: a bi-objective approach
• Shortest-path network interdiction
• Optimal \(K\)-node disruption on a node-capacitated network
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Optimal detection of critical nodes: improvements to model structure and performance

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• A cutting plane algorithm for computing \(k\)-edge survivability of a network
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Detecting critical nodes in sparse graphs
• Deterministic network interdiction
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Finding the most vital arcs in a network
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Identifying sets of key players in a social network
• Interior point stabilization for column generation
• Maximal Flow Through a Network
• Optimal interdiction of a supply network
• Removing Arcs from a Network
• Selected Topics in Column Generation
• Shortest-path network interdiction
• Solving the bi-objective maximum-flow network-interdiction problem

Cited in

(17)

• The all-pairs vitality-maximization (VIMAX) problem
• Finding the most degree-central walks and paths in a graph: exact and heuristic approaches
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Optimal detection of critical nodes: improvements to model structure and performance
• A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem
• The stochastic critical node problem over trees
• Efficient network disruption under imperfect information: the sharpening effect of network reconstruction with no prior knowledge
• A mixed-integer programming approach for locating jamming devices in a flow-jamming attack
• A bi-level model and memetic algorithm for arc interdiction location-routing problem
• A study of network violator interception based on a reliable game model
• Detecting critical node structures on graphs: a mathematical programming approach
• Determining the most vital arcs on the shortest path for fire trucks in terrorist actions that will cause fire
• Sequential Shortest Path Interdiction with Incomplete Information
• Network interdiction through length-bounded critical disruption paths: a bi-objective approach
• A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
• The connected critical node problem
• Optimal \(K\)-node disruption on a node-capacitated network

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: Network interdiction via a critical disruption path: branch-and-price algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q336604)