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
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, Blocking unions of arborescences, Connectivity interdiction, Perfect matching interdiction problem restricted to a stable vertex, Critical edges for the assignment problem: complexity and exact resolution, Bulk-robust combinatorial optimization, 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
