Branch and cut algorithms for detecting critical nodes in undirected graphs
From MaRDI portal
Publication:1935569
DOI10.1007/s10589-012-9458-yzbMath1264.90170OpenAlexW2065419861MaRDI QIDQ1935569
Marco Di Summa, Marco Locatelli, Andrea Grosso
Publication date: 18 February 2013
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10589-012-9458-y
Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items (40)
Complexity of the multilevel critical node problem ⋮ Hybrid constructive heuristics for the critical node problem ⋮ Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Minimum edge blocker dominating set problem ⋮ A genetic algorithm for a class of critical node problems ⋮ Network interdiction via a critical disruption path: branch-and-price algorithms ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ 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 ⋮ Solving the Distance-Based Critical Node Problem ⋮ A Region Growing Algorithm for Detecting Critical Nodes ⋮ A Fast Greedy Algorithm for the Critical Node Detection Problem ⋮ 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 ⋮ Critical node/edge detection problems on trees ⋮ Design/upgrade of a transparent optical network topology resilient to the simultaneous failure of its critical nodes ⋮ Content placement in 5G‐enabled edge/core data center networks resilient to link cut attacks ⋮ 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 ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ On designing networks resilient to clique blockers ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ A fast tri-individual memetic search approach for the distance-based critical node problem ⋮ Exact identification of critical nodes in sparse networks via new compact formulations ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Compact models for critical node detection in telecommunication networks ⋮ The critical node detection problem in networks: a survey ⋮ An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections ⋮ Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem ⋮ 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 ⋮ Robust Critical Node Selection by Benders Decomposition ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
Uses Software
Cites Work
- Enhancing RLT-based relaxations for polynomial programming problems via a new class of \(v\)-semidefinite cuts
- Enhancing RLT relaxations via a new class of semidefinite cuts
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
- A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
- Deterministic network interdiction
- A cutting plane algorithm for computing \(k\)-edge survivability of a network
- A reformulation-convexification approach for solving nonconvex quadratic programming problems
- Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Graph Theory and Integer Programming
- CSDP, A C library for semidefinite programming
- Removing Arcs from a Network
- Combinatorial optimization. Theory and algorithms
This page was built for publication: Branch and cut algorithms for detecting critical nodes in undirected graphs
