Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem

DOI10.1016/j.cor.2012.02.008zbMath1251.90342MaRDI QIDQ1761226

Mario Ventresca

Publication date: 15 November 2012

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

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

zbMATH Keywords

simulated annealing; random graph; complex networks; critical node detection; population-based incremental learning

Mathematics Subject Classification ID

05C82: Small world graphs, complex networks (graph-theoretic aspects)

05C80: Random graphs (graph-theoretic aspects)

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Detecting critical node structures on graphs: A mathematical programming approach, Hybrid constructive heuristics for the critical node problem, A genetic algorithm for a class of critical node problems, A derandomized approximation algorithm for the critical node detection problem, A randomized algorithm with local search for containment of pandemic disease spread, An integer programming framework for critical elements detection in graphs, Parameterized complexity of critical node cuts, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, The bi-objective critical node detection problem, Efficient heuristic algorithm for identifying critical nodes in planar networks, The critical node detection problem in networks: a survey, Literature review: the vaccine supply chain, Optimizing node infiltrations in complex networks by a local search based heuristic, A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs, Exact identification of critical nodes in sparse networks via new compact formulations, VNS solutions for the critical node problem, Robust Critical Node Selection by Benders Decomposition, A Region Growing Algorithm for Detecting Critical Nodes, A Fast Greedy Algorithm for the Critical Node Detection Problem

Uses Software

• Stony Brook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Complexity of the critical node problem over trees
• Detecting critical nodes in sparse graphs
• A calculus for the random generation of labelled combinatorial structures
• Ranking and unranking permutations in linear time
• Evolution of the social network of scientific collaborations
• Efficient immunization strategies on complex networks
• 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
• Cardinality-Constrained Critical Node Detection Problem
• Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
• Emergence of Scaling in Random Networks
• A random graph model for massive graphs
• Handbook of Applied Algorithms
• A comparison of simulated annealing cooling strategies
• Parallel Processing and Applied Mathematics
• Collective dynamics of ‘small-world’ networks