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

DOI10.1142/S0217595920500414MaRDI QIDQ5012889zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

treedynamic programmingcritical node problemconnectivity index

Mathematics Subject Classification ID

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

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

Cites work

• An integer programming framework for critical elements detection in graphs
• Complexity and approximability of the \(k\)-way vertex cut
• Complexity of the critical node problem over trees
• Component-cardinality-constrained critical node problem in graphs
• Detecting critical node structures on graphs: a mathematical programming approach
• Detecting critical nodes in sparse graphs
• Epidemic dynamics on complex networks
• 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
• Identifying sets of key players in a social network
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• The bi-objective critical node detection problem
• The critical node detection problem in networks: a survey

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
• The connected critical node problem
• On critical node problems with vulnerable vertices

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)