Solving the Distance-Based Critical Node Problem

DOI10.1287/ijoc.2021.1136OpenAlexW4205905697MaRDI QIDQ5087707

Austin Buchanan, Hosseinali Salemi

Publication date: 1 July 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2021.1136

zbMATH Keywords

branch-and-cutinteger programdominantnetwork interdictioncritical nodedistance constraintpartial dominant

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (3)

Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ A polytime preprocess algorithm for the maximum independent set problem ⋮ A fast tri-individual memetic search approach for the distance-based critical node problem

Uses Software

• Pajek
• Pajek datasets
• SparseMatrix
• DIMACS
• GitHub

Cites Work

• Unnamed Item
• Identifying sets of key players in a social network
• Hybrid constructive heuristics for the critical node problem
• Complexity of the critical node problem over trees
• Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
• Detecting critical nodes in sparse graphs
• Geometric algorithms and combinatorial optimization.
• On the monotonization of polyhedra
• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
• Thinning out Steiner trees: a node-based model for uniform edge costs
• The critical node detection problem in networks: a survey
• An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Parsimonious formulations for low-diameter clusters
• The wireless network jamming problem
• 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
• Epidemic dynamics on complex networks
• Efficient methods for the distance-based critical node detection problem in complex networks
• A faster algorithm for betweenness centrality*
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• The university of Florida sparse matrix collection
• Length-bounded cuts and flows
• Detecting critical node structures on graphs: A mathematical programming approach
• The Optimal Design of Low-Latency Virtual Backbones
• Imposing Connectivity Constraints in Forest Planning Models
• Selected Topics in Critical Element Detection
• Extended formulations in combinatorial optimization

This page was built for publication: Solving the Distance-Based Critical Node Problem