The critical node detection problem in networks: a survey
From MaRDI portal
Publication:1750314
DOI10.1016/j.cosrev.2018.02.002zbMath1387.68186OpenAlexW2792824988MaRDI QIDQ1750314
Hamamache Kheddouci, Mohammed Lalou, Mohammed Amin Tahraoui
Publication date: 18 May 2018
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2018.02.002
complexitycombinatorial optimizationapproximation schemesgraph connectivitycomplex networknode-deletion problemcritical nodeimportant node
Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Complexity of the multilevel critical node problem, Critical node detection problem for complex network in undirected weighted networks, On critical node problems with vulnerable vertices, Solving the Distance-Based Critical Node Problem, The minimum cost network upgrade problem with maximum robustness to multiple node failures, Integer programming methods for solving binary interdiction games, The connected critical node problem, Critical node/edge detection problems on trees, The firebreak problem, A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem, The stochastic critical node problem over trees, Assistance and interdiction problems on interval graphs, Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items, A survey on mixed-integer programming techniques in bilevel optimization, Strong Connectivity in Directed Graphs under Failures, with Applications, On integer and bilevel formulations for the \(k\)-vertex cut problem, Min–max optimization of node‐targeted attacks in service networks, Maximizing SDN resilience to node‐targeted attacks through joint optimization of the primary and backup controllers placements, Analysis of cluster damages in network systems, 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, Efficient heuristic algorithm for identifying critical nodes in planar networks, The maximum clique interdiction problem, Analysis of critical damage in the communication network. III: Analysis of internode flows, Analysis of critical damage in the communication network. I: Model and computational experiment, Construction of simple path graphs in transport networks. I: General solutions and examples, Optimizing node infiltrations in complex networks by a local search based heuristic, Critical nodes in interdependent networks with deterministic and probabilistic cascading failures, EIA-CNDP: an exact iterative algorithm for critical node detection problem, An approach to the analysis of possible structural damages in multicommodity network systems, 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Identifying sets of key players in a social network
- Hybrid constructive heuristics for the critical node problem
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Component-cardinality-constrained critical node problem in graphs
- A derandomized approximation algorithm for the critical node detection problem
- A randomized algorithm with local search for containment of pandemic disease spread
- An integer programming framework for critical elements detection in graphs
- Restricted vertex multicut on permutation graphs
- Graph clustering
- A preliminary analysis of the distance based critical node problem
- Parameterized complexity of critical node cuts
- Complexity of the critical node problem over trees
- An exact algorithm for solving the vertex separator problem
- A multi-criteria optimization model for humanitarian aid distribution
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Minimal multicut and maximal integer multiflow: a survey
- On the computational complexity of vertex integrity and component order connectivity
- Weakly triangulated graphs
- On the hardness of approximating minimum vertex cover
- Parameterized graph separation problems
- The multi-multiway cut problem
- On short paths interdiction problems: Total and node-wise limited interdiction
- Maximally edge-connected and vertex-connected graphs and digraphs: A survey
- Variable neighbourhood search: methods and applications
- Chordal deletion is fixed-parameter tractable
- Simple and improved parameterized algorithms for multiterminal cuts
- Detecting critical nodes in sparse graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- The node-deletion problem for hereditary properties is NP-complete
- Most vital links and nodes in weighted networks
- Unit disk graphs
- Finding good approximate vertex and edge partitions is NP-hard
- A survey of integrity
- The bi-objective critical node detection problem
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- Deterministic network interdiction
- A cutting plane algorithm for computing \(k\)-edge survivability of a network
- Algorithmic graph theory and perfect graphs
- Extended formulations for the \(A\)-cut problem
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Branch and cut algorithms for detecting critical nodes in undirected graphs
- An improved parameterized algorithm for the minimum node multiway cut problem
- The wireless network jamming problem
- A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm
- Obtaining a planar graph by vertex deletion
- 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
- Epidemic dynamics on complex networks
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- The vertex separator problem: algorithms and computations
- The vertex separator problem: a polyhedral investigation
- Parametrized complexity theory.
- VNS solutions for the critical node problem
- A faster algorithm for betweenness centrality*
- A Region Growing Algorithm for Detecting Critical Nodes
- A Fast Greedy Algorithm for the Critical Node Detection Problem
- The university of Florida sparse matrix collection
- Cardinality-Constrained Critical Node Detection Problem
- Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
- The small-world phenomenon
- An improved algorithm for the planar 3-cut problem
- Fixed-parameter tractability and data reduction for multicut in trees
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
- Treewidth: Characterizations, Applications, and Computations
- Graph minors. II. Algorithmic aspects of tree-width
- On graphs with polynomially solvable maximum-weight clique problem
- Graph Bipartization and via minimization
- Node-Deletion NP-Complete Problems
- A Separator Theorem for Planar Graphs
- Node-Deletion Problems on Bipartite Graphs
- On the multiway cut polyhedron
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Complexity and approximability of the k‐way vertex cut
- Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
- Computing Critical Nodes in Directed Graphs
- Rumors in a Network: Who's the Culprit?
- NP-completeness of the Planar Separator Problems
- Node-and edge-deletion NP-complete problems
- Disconnecting graphs by removing vertices: a polyhedral approach
- Approximating Betweenness Centrality
- Automata, Languages and Programming
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
