Matching interdiction
From MaRDI portal
Publication:602686
DOI10.1016/j.dam.2010.06.006zbMath1208.05120MaRDI 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
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W25: Approximation algorithms
Related Items
Detecting critical node structures on graphs: A mathematical programming approach, Unnamed Item, Multilevel Approaches for the Critical Node Problem, On the Independent Set Interdiction Problem, Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal, Integer Programming Formulations for Minimum Spanning Tree Interdiction, A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games, Interdiction Games and Monotonicity, with Application to Knapsack Problems, 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, A survey on mixed-integer programming techniques in bilevel optimization, Minimum edge blocker dominating set problem, The most vital nodes with respect to independent set and vertex cover, On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph, 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, Interdiction problems on planar graphs, Exact algorithms for the minimum cost vertex blocker clique problem, A note on linearized reformulations for a class of bilevel linear integer problems, Blocking unions of arborescences, Connectivity interdiction, Perfect matching interdiction problem restricted to a stable vertex, 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, Minimum \(k\)-critical bipartite graphs, The continuous maximum capacity path interdiction problem, Colored cut games, Using edge contractions to reduce the semitotal domination number, Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance, A survey of network interdiction models and algorithms, Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut, Critical edges for the assignment problem: complexity and exact resolution, Bulk-robust combinatorial optimization, Integer programming methods for solving binary interdiction games, Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges, 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, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Study of the Matching Interdiction Problem in Some Molecular Graphs of Dendrimers
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