Matching interdiction
From MaRDI portal
Publication:602686
DOI10.1016/j.dam.2010.06.006zbMath1208.05120OpenAlexW2915069302MaRDI QIDQ602686
Publication date: 5 November 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.06.006
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items
Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Minimum edge blocker dominating set problem ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games ⋮ Integer programming methods for solving binary interdiction games ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ Vertex downgrading to minimize connectivity ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ Logic-based Benders decomposition for wildfire suppression ⋮ On designing networks resilient to clique blockers ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Interdiction problems on planar graphs ⋮ Unnamed Item ⋮ An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph ⋮ Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives ⋮ Study of the Matching Interdiction Problem in Some Molecular Graphs of Dendrimers ⋮ Critical edges for the assignment problem: complexity and exact resolution ⋮ Interdiction Games and Monotonicity, with Application to Knapsack Problems ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ A note on linearized reformulations for a class of bilevel linear integer problems ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ Blockers for the stability number and the chromatic number ⋮ Blocking optimal arborescences ⋮ Analysis of budget for interdiction on multicommodity network flows ⋮ A simple greedy heuristic for linear assignment interdiction ⋮ Blocking unions of arborescences ⋮ Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Connectivity interdiction ⋮ Perfect matching interdiction problem restricted to a stable vertex ⋮ Bulk-robust combinatorial optimization ⋮ Minimum \(k\)-critical bipartite graphs ⋮ A survey of network interdiction models and algorithms ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Multilevel Approaches for the Critical Node Problem ⋮ The continuous maximum capacity path interdiction problem ⋮ Colored cut games ⋮ On the Independent Set Interdiction Problem ⋮ Using edge contractions to reduce the semitotal domination number
Cites Work
- Unnamed Item
- Unnamed Item
- A factor 2 approximation algorithm for the generalized Steiner network problem
- On short paths interdiction problems: Total and node-wise limited interdiction
- The 0-1 inverse maximum stable set problem
- Network flow interdiction on planar graphs
- Blockers and transversals
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- The node-deletion problem for hereditary properties is NP-complete
- The most vital edges in the minimum spanning tree problem
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Deterministic network interdiction
- Finding the most vital arcs in a network
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- NP-completeness results for edge modification problems
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Edge-Deletion Problems
- Node-Deletion Problems on Bipartite Graphs
- Maximizing the minimum source-sink path subject to a budget constraint
- A problem in network interdiction
- Shortest-path network interdiction
- The network inhibition problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Complexity classification of some edge modification problems
