Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
From MaRDI portal
Publication:1634769
DOI10.1016/j.dam.2017.12.035zbMath1401.05089OpenAlexW2792628671MaRDI QIDQ1634769
Rosario Scatamacchia, Pierre Hosteins, Roberto Aringhieri, Andrea Grosso
Publication date: 18 December 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2017.12.035
dynamic programmingshortest pathspolynomial time algorithmscritical node problemconnectivity measure
Related Items (10)
Complexity of the multilevel critical node problem ⋮ Interdicting facilities in tree networks ⋮ Solving the Distance-Based Critical Node Problem ⋮ Efficient methods for the distance-based critical node detection problem in complex networks ⋮ The connected critical node problem ⋮ Critical node/edge detection problems on trees ⋮ The stochastic critical node problem over trees ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ A fast tri-individual memetic search approach for the distance-based critical node problem ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
Cites Work
- Identifying sets of key players in a social network
- Hybrid constructive heuristics for the critical node problem
- Component-cardinality-constrained critical node problem in graphs
- A genetic algorithm for a class of critical node problems
- An integer programming framework for critical elements detection in graphs
- A preliminary analysis of the distance based critical node problem
- Complexity of the critical node problem over trees
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- On some counting polynomials in chemistry
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- Deterministic network interdiction
- Efficiency of scale-free networks: Error and attack tolerance
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- Epidemic dynamics on complex networks
- VNS solutions for the critical node problem
- Stochastic Network Interdiction
- Cardinality-Constrained Critical Node Detection Problem
- The Recognition of Series Parallel Digraphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- The Structure and Function of Complex Networks
- Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
- Removing Arcs from a Network
This page was built for publication: Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
