Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
DOI10.1016/j.disopt.2019.100551zbMath1506.05174OpenAlexW2966633405MaRDI QIDQ2299979
Publication date: 24 February 2020
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2019.100551
bipartite graphpolytopeinteger linear programmingbranch-and-cutmatching interdiction/blocker problem
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- Blockers for the stability number and the chromatic number
- Matching interdiction
- On short paths interdiction problems: Total and node-wise limited interdiction
- Blockers and transversals
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Matching theory
- The ellipsoid method and its consequences in combinatorial optimization
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions
- A Note on n-Critical Bipartite Graphs and Its Application
- A Contribution to the Theory of Groups of Prime-Power Order
- Maximum matching and a polyhedron with 0,1-vertices
This page was built for publication: Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
