Component-cardinality-constrained critical node problem in graphs

DOI10.1016/J.DAM.2015.01.043zbMATH Open1339.05374OpenAlexW2063077688MaRDI QIDQ299073FDOQ299073

Authors: H. Kheddouci, M. Lalou, M. A. Tahraoui 

Publication date: 22 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.01.043

Recommendations

• The critical node problem based on connectivity index and properties of components on trees
• Complexity of the critical node problem over trees
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth

zbMATH Keywords

complexityvertex cover problemchordal graphscritical nodes

Mathematics Subject Classification ID

Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Signed and weighted graphs (05C22)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Graph theory
• Identifying sets of key players in a social network
• Automata, Languages and Programming
• On the hardness of approximating minimum vertex cover
• Detecting critical nodes in sparse graphs
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• The wireless network jamming problem
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• A Separator Theorem for Planar 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
• The clique-separator graph for chordal graphs
• Most vital links and nodes in weighted networks
• The vertex separator problem: algorithms and computations
• Cardinality-Constrained Critical Node Detection Problem
• Robust optimization of graph partitioning and critical node detection in analyzing networks

Cited In (15)

• EIA-CNDP: an exact iterative algorithm for critical node detection problem
• Solving the Distance-Based Critical Node Problem
• Hybrid constructive heuristics for the critical node problem
• Complexity of the critical node problem over trees
• Critical node detection problem for complex network in undirected weighted networks
• Complexity of the multilevel critical node problem
• The stochastic critical node problem over trees
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
• The minimum cost network upgrade problem with maximum robustness to multiple node failures
• Critical node/edge detection problems on trees
• The critical node problem based on connectivity index and properties of components on trees
• The connected critical node problem
• The critical node detection problem in networks: a survey
• Computing Critical Nodes in Directed Graphs

This page was built for publication: Component-cardinality-constrained critical node problem in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299073)