Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem

DOI10.1016/J.DAM.2017.12.035MaRDI QIDQ1634769zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dynamic programmingshortest pathscritical node problempolynomial time algorithmsconnectivity measure

Mathematics Subject Classification ID

Dynamic programming (90C39) Distance in graphs (05C12) Connectivity (05C40)

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

Cites work

• A genetic algorithm for a class of critical node problems
• A preliminary analysis of the distance based critical node problem
• An integer programming framework for critical elements detection in graphs
• Cardinality-Constrained Critical Node Detection Problem
• Complexity of the critical node problem over trees
• Component-cardinality-constrained critical node problem in graphs
• Detecting critical nodes in sparse graphs
• Deterministic network interdiction
• Efficiency of scale-free networks: Error and attack tolerance
• Epidemic dynamics on complex networks
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Hybrid constructive heuristics for the critical node problem
• 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
• Linear-time computability of combinatorial problems on series-parallel graphs
• Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
• On some counting polynomials in chemistry
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• Removing Arcs from a Network
• Stochastic network interdiction
• The Recognition of Series Parallel Digraphs
• The Structure and Function of Complex Networks
• VNS solutions for the critical node problem

Cited in

(13)

• Interdicting facilities in tree networks
• A fast tri-individual memetic search approach for the distance-based critical node problem
• Complexity of the multilevel critical node problem
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• The stochastic critical node problem over trees
• Efficient methods for the distance-based critical node detection problem in complex networks
• Critical node/edge detection problems on trees
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• A genetic algorithm for a class of critical node problems
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Solving the Distance-Based Critical Node Problem
• 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)