Component-cardinality-constrained critical node problem in graphs

DOI10.1016/J.DAM.2015.01.043MaRDI QIDQ299073zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• A Separator Theorem for Planar Graphs
• Automata, Languages and Programming
• Cardinality-Constrained Critical Node Detection Problem
• Complexity of the critical node problem over trees
• Detecting critical nodes in sparse graphs
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Graph theory
• 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
• Most vital links and nodes in weighted networks
• Network flows. Theory, algorithms, and applications.
• On the hardness of approximating minimum vertex cover
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• Robust optimization of graph partitioning and critical node detection in analyzing networks
• The clique-separator graph for chordal graphs
• The vertex separator problem: algorithms and computations
• The wireless network jamming problem

Cited in

(15)

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

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)