The critical node problem based on connectivity index and properties of components on trees

DOI10.1142/S0217595920500414zbMATH Open1481.90275OpenAlexW3048608145MaRDI QIDQ5012889FDOQ5012889

Authors: Xiucui Guan, Chao Liu, Qiao Zhang 

Publication date: 26 November 2021

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0217595920500414

Recommendations

• Complexity of the critical node problem over trees
• Component-cardinality-constrained critical node problem in 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
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth

zbMATH Keywords

treedynamic programmingcritical node problemconnectivity index

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Identifying sets of key players in a social network
• Detecting critical nodes in sparse graphs
• 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
• Component-cardinality-constrained critical node problem in graphs
• 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
• The bi-objective critical node detection problem
• The critical node detection problem in networks: a survey
• Epidemic dynamics on complex networks
• Complexity and approximability of the \(k\)-way vertex cut
• Detecting critical node structures on graphs: a mathematical programming approach

Cited In (7)

• Component-cardinality-constrained critical node problem in graphs
• Complexity of the critical node problem over trees
• Critical node/edge detection problems on trees
• 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
• On critical node problems with vulnerable vertices
• The connected critical node problem

This page was built for publication: The critical node problem based on connectivity index and properties of components on trees

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