A Fast Greedy Algorithm for the Critical Node Detection Problem

DOI10.1007/978-3-319-12691-3_45zbMath1433.05302OpenAlexW792477341MaRDI QIDQ2942435

Mario Ventresca, Dionne M. Aleman

Publication date: 11 September 2015

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-12691-3_45

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Critical node detection problem for complex network in undirected weighted networks, The bi-objective critical node detection problem, A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem, The critical node detection problem in networks: a survey, EIA-CNDP: an exact iterative algorithm for critical node detection problem

Cites Work

• Unnamed Item
• Unnamed Item
• A derandomized approximation algorithm for the critical node detection problem
• A randomized algorithm with local search for containment of pandemic disease spread
• Bound and exact methods for assessing link vulnerability in complex networks
• An integer programming framework for critical elements detection in graphs
• Complexity of the critical node problem over trees
• Detecting critical nodes in sparse graphs
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Exact identification of critical nodes in sparse networks via new compact formulations
• Authoritative sources in a hyperlinked environment
• Collective dynamics of ‘small-world’ networks
• Depth-First Search and Linear Graph Algorithms