Blockers and transversals
From MaRDI portal
Publication:1043948
DOI10.1016/j.disc.2009.01.006zbMath1204.05085OpenAlexW2067622223MaRDI QIDQ1043948
Cédric Bentz, Bernard Ries, Dominique de Werra, Rico Zenklusen, Christophe Picouleau, Marie-Christine Costa
Publication date: 10 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://doc.rero.ch/record/324622/files/blockersandtransversalsi.pdf
Related Items (34)
On the complexity of the identifiable subgraph problem, revisited ⋮ Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs ⋮ Minimum edge blocker dominating set problem ⋮ Using edge contractions and vertex deletions to reduce the independence number and the clique number ⋮ Matching interdiction ⋮ On anti-Kekulé and \(s\)-restricted matching preclusion problems ⋮ Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem ⋮ Connections between graphs and matrix spaces ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Reducing graph parameters by contractions and deletions ⋮ On the NP-completeness of the perfect matching free subgraph problem ⋮ An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems ⋮ Feedback robustness in structured closed-loop system ⋮ Critical edges for the assignment problem: complexity and exact resolution ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures ⋮ Blockers for the stability number and the chromatic number ⋮ Blocking optimal arborescences ⋮ Blocking unions of arborescences ⋮ Unnamed Item ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Connectivity interdiction ⋮ Minimum \(k\)-critical bipartite graphs ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Relating dissociation, independence, and matchings ⋮ Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid ⋮ Safety in \(s\)-\(t\) paths, trails and walks
Cites Work
- Unnamed Item
- Unnamed Item
- On complexity of special maximum matchings constructing
- The 0-1 inverse maximum stable set problem
- The node-deletion problem for hereditary properties is NP-complete
- NP-completeness results for edge modification problems
- Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- Edge-Deletion Problems
- Node-Deletion Problems on Bipartite Graphs
- Paths, Trees, and Flowers
- Bicolored matchings in some classes of graphs
- Complexity classification of some edge modification problems
This page was built for publication: Blockers and transversals
