Detecting critical node structures on graphs: A mathematical programming approach
From MaRDI portal
Publication:4628045
DOI10.1002/net.21834zbMath1407.90093OpenAlexW2889920478MaRDI QIDQ4628045
Alexander Veremyev, Eduardo L. Pasiliao, Jose L. Walteros, Panos M. Pardalos
Publication date: 6 March 2019
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.21834
combinatorial optimizationgraph partitioningmixed-integer programmingcritical node problembranch-price-and-cutnetwork interdiction
Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items
Solving the Distance-Based Critical Node Problem, Integer programming methods for solving binary interdiction games, A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem, Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches, The stochastic critical node problem over trees, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Construction of simple path graphs in transport networks. I: General solutions and examples, The Critical Node Problem Based on Connectivity Index and Properties of Components on Trees
Uses Software
Cites Work
- Identifying sets of key players in a social network
- Minimum edge blocker dominating set problem
- Network interdiction via a critical disruption path: branch-and-price algorithms
- A derandomized approximation algorithm for the critical node detection problem
- An integer programming framework for critical elements detection in graphs
- Nodal interdiction
- The most vital nodes with respect to independent set and vertex cover
- Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
- Complexity of the critical node problem over trees
- Matching interdiction
- A tutorial on column generation and branch-and-price for vehicle routing problems
- Facets of the clique partitioning polytope
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- Blockers and transversals
- The node-deletion problem for hereditary properties is NP-complete
- Most vital links and nodes in weighted networks
- Stabilized column generation
- Cluster analysis and mathematical programming
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- The critical node detection problem in networks: a survey
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- Deterministic network interdiction
- A cutting plane algorithm for computing \(k\)-edge survivability of a network
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Branch and cut algorithms for detecting critical nodes in undirected graphs
- Integer programming models for the multidimensional assignment problem with star costs
- 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
- Interior point stabilization for column generation
- Branch-and-Price: Column Generation for Solving Huge Integer Programs
- Robust Critical Node Selection by Benders Decomposition
- The university of Florida sparse matrix collection
- How to Cut a Graph into Many Pieces
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- Statistical mechanics of complex networks
- Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods
- The B<scp>oxstep</scp> Method for Large-Scale Optimization
- The centrality of groups and classes
- Minimum vertex blocker clique problem
- Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
- A set‐partitioning‐based exact algorithm for the vehicle routing problem
- Shortest-path network interdiction
- Increasing the Weight of Minimum Spanning Trees
- The Valve Location Problem in Simple Network Topologies
- Selected Topics in Column Generation
- Collective dynamics of ‘small-world’ networks
- Disconnecting graphs by removing vertices: a polyhedral approach
- Removing Arcs from a Network
- Technical Note—“Linear” Programming with Absolute-Value Functionals
- A Modified Linear Program for Columnar Methods in Mathematical Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
