Efficient heuristic algorithm for identifying critical nodes in planar networks

DOI10.1016/J.COR.2019.02.006MaRDI QIDQ1734834zbMATH OpenOpenAlexWikidataFDO

Authors Dalaijargal Purevsuren, Gang Cui

Publication date 27 March 2019

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2019.02.006

zbMATH Keywords

combinatorial optimizationcritical node detectionheuristicsNP-completeplanar networks

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A derandomized approximation algorithm for the critical node detection problem
• A fast greedy algorithm for the critical node detection problem
• Hybrid constructive heuristics for the critical node problem
• Detecting critical nodes in sparse graphs
• Optimal detection of critical nodes: improvements to model structure and performance

Cites work

• A Separator Theorem for Planar Graphs
• Detecting critical nodes in sparse graphs
• Discrete and computational geometry
• Engineering planar separator algorithms
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Hybrid constructive heuristics for the critical node problem
• Some simplified NP-complete graph problems
• The bi-objective critical node detection problem
• The critical node detection problem in networks: a survey

Cited in

(5)

• Identifying influential spreaders in complex networks based on improved k-shell method
• Critical node detection problem for complex network in undirected weighted networks
• The minimum cost network upgrade problem with maximum robustness to multiple node failures
• Hybrid constructive heuristics for the critical node problem
• A preliminary analysis of the distance based critical node problem

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Efficient heuristic algorithm for identifying critical nodes in planar networks

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