Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
DOI10.1016/J.DAM.2017.12.035zbMATH Open1401.05089OpenAlexW2792628671MaRDI QIDQ1634769FDOQ1634769
Authors: Roberto Aringhieri, Andrea Grosso, Pierre Hosteins, Rosario Scatamacchia 
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
Recommendations
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- A preliminary analysis of the distance based critical node problem
- Complexity of the critical node problem over trees
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
dynamic programmingshortest pathscritical node problempolynomial time algorithmsconnectivity measure
Cites Work
- The Structure and Function of Complex Networks
- Identifying sets of key players in a social network
- Efficiency of scale-free networks: Error and attack tolerance
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- Deterministic network interdiction
- 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
- VNS solutions for the critical node problem
- 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
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- Complexity of the critical node problem over trees
- Removing Arcs from a Network
- The Recognition of Series Parallel Digraphs
- Stochastic network interdiction
- On some counting polynomials in chemistry
- Cardinality-Constrained Critical Node Detection Problem
- Epidemic dynamics on complex networks
- Linear-time computability of combinatorial problems on series-parallel graphs
- A preliminary analysis of the distance based critical node problem
Cited In (13)
- Solving the Distance-Based Critical Node Problem
- Efficient methods for the distance-based critical node detection problem in complex networks
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- A genetic algorithm for a class of critical node problems
- Complexity of the multilevel critical node problem
- The stochastic critical node problem over trees
- 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
- Critical node/edge detection problems on trees
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- Interdicting facilities in tree networks
- The connected critical node problem
- A preliminary analysis of the distance based critical node problem
This page was built for publication: Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1634769)
