Component-cardinality-constrained critical node problem in graphs

DOI10.1016/j.dam.2015.01.043zbMath1339.05374OpenAlexW2063077688MaRDI QIDQ299073

Hamamache Kheddouci, Mohammed Lalou, Mohammed Amin 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

zbMATH Keywords

complexitychordal graphsvertex cover problemcritical nodes

Mathematics Subject Classification ID

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

Related Items (11)

Complexity of the multilevel critical node problem ⋮ Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem ⋮ Critical node detection problem for complex network in undirected weighted networks ⋮ The minimum cost network upgrade problem with maximum robustness to multiple node failures ⋮ The connected critical node problem ⋮ Critical node/edge detection problems on trees ⋮ The stochastic critical node problem over trees ⋮ The critical node detection problem in networks: a survey ⋮ EIA-CNDP: an exact iterative algorithm for critical node detection problem ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Identifying sets of key players in a social network
• Complexity of the critical node problem over trees
• On the hardness of approximating minimum vertex cover
• Detecting critical nodes in sparse graphs
• The clique-separator graph for chordal graphs
• Most vital links and nodes in weighted networks
• 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
• 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
• A Separator Theorem for Planar Graphs
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Automata, Languages and Programming

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