Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
From MaRDI portal
Publication:1045154
DOI10.1016/j.disc.2009.08.009zbMath1223.05240OpenAlexW2038483792MaRDI QIDQ1045154
Cédric Bentz, Rico Zenklusen, Dominique de Werra, Marie-Christine Costa, Bernard Ries, Christophe Picouleau
Publication date: 15 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://doc.rero.ch/record/326878/files/blockersandtransversalsii.pdf
Related Items (31)
Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Minimum edge blocker dominating set problem ⋮ Matching interdiction ⋮ Reducing the chromatic number by vertex or edge deletions ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ Reducing the vertex cover number via edge contractions ⋮ On designing networks resilient to clique blockers ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ 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 ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions ⋮ Critical edges for the assignment problem: complexity and exact resolution ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ 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 ⋮ Unnamed Item ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Blocking total dominating sets via edge contractions ⋮ Reducing graph transversals via edge contractions ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Using edge contractions to reduce the semitotal domination number
Cites Work
- Unnamed Item
- Blockers and transversals
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Additive approximation for edge-deletion problems
- NP-completeness results for edge modification problems
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- Edge-Deletion Problems
- Complexity classification of some edge modification problems
This page was built for publication: Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
