Integer Programming Formulations for Minimum Spanning Tree Interdiction
From MaRDI portal
Publication:5084609
DOI10.1287/ijoc.2020.1018OpenAlexW3134880487MaRDI QIDQ5084609
Jose L. Walteros, Ningji Wei, Foad Mahdavi Pajouh
Publication date: 28 June 2022
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.2020.1018
Related Items (6)
Integer programming methods for solving binary interdiction games ⋮ Exact solution approaches for a class of bilevel fractional programs ⋮ Shortest path interdiction problem with convex piecewise-linear costs ⋮ Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds ⋮ On designing networks resilient to clique blockers ⋮ Parametric matroid interdiction
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum edge blocker dominating set problem
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- An integer programming framework for critical elements detection in graphs
- Nodal interdiction
- The most vital nodes with respect to independent set and vertex cover
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Matching interdiction
- Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure
- Detecting critical nodes in sparse graphs
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Finding the k most vital edges in the minimum spanning tree problem
- Most vital links and nodes in weighted networks
- The discipline number of a graph
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
- The most vital edges in the minimum spanning tree problem
- Efficient algorithms for finding the most vital edge of a minimum spanning tree
- Compact vs. exponential-size LP relaxations
- The maximum clique interdiction problem
- Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
- Deterministic network interdiction
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Branch and cut algorithms for detecting critical nodes in undirected graphs
- The \(k\)-separator problem: polyhedra, complexity and approximation results
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- Epidemic dynamics on complex networks
- Stochastic Network Interdiction
- Mixed Integer Linear Programming Formulation Techniques
- Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- Statistical mechanics of complex networks
- A linear programming approach to increasing the weight of all minimum spanning trees
- Worst-case Analysis of Set Union Algorithms
- Multi-Terminal Network Flows
- An Algorithm for Finding K Minimum Spanning Trees
- Minimum vertex blocker clique problem
- On the History of the Minimum Spanning Tree Problem
- Shortest-path network interdiction
- Increasing the Weight of Minimum Spanning Trees
- The constrained minimum spanning tree problem
- Improved Algorithms for MST and Metric-TSP Interdiction
- Collective dynamics of ‘small-world’ networks
- Disconnecting graphs by removing vertices: a polyhedral approach
- Random Graphs
- Removing Arcs from a Network
- Optimal interdiction policy for a flow network
- The Traveling-Salesman Problem and Minimum Spanning Trees
- A Backward Sampling Framework for Interdiction Problems with Fortification
This page was built for publication: Integer Programming Formulations for Minimum Spanning Tree Interdiction