Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid

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

zbMATH Keywords

treematchingtransversalcaterpillargrid graphblocker

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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