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.009zbMATH Open1223.05240OpenAlexW2038483792MaRDI QIDQ1045154FDOQ1045154
Authors: Cédric Bentz, Bernard Ries, Christophe Picouleau, Dominique De Werra, Marie-Christine Costa, Rico Zenklusen 
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
Recommendations
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
- Block transitivity and degree matrices
- Blocks in \(k\)-connected graphs
- On Pebbling Graphs by Their Blocks
- On the block number of graphs
- scientific article; zbMATH DE number 3891428
- scientific article; zbMATH DE number 6000604
- scientific article; zbMATH DE number 1792672
- An observation on block graphs
Cites Work
- Blockers and transversals
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity classification of some edge modification problems
- Title not available (Why is that?)
- NP-completeness results for edge modification problems
- Edge-Deletion Problems
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- Additive approximation for edge-deletion problems
Cited In (34)
- Minimum cost edge blocker clique problem
- Using edge contractions to reduce the semitotal domination number
- Title not available (Why is that?)
- Algorithms – ESA 2004
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
- On blockers and transversals of maximum independent sets in co-comparability graphs
- Critical vertices and edges in \(H\)-free graphs
- Blockers and transversals
- Reducing the vertex cover number via edge contractions
- Reducing the chromatic number by vertex or edge deletions
- Exact algorithms for the minimum cost vertex blocker clique problem
- Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Complexity of most vital nodes for independent set in graphs related to tree structures
- Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems
- Minimum edge blocker dominating set problem
- Blocking total dominating sets via edge contractions
- Reducing graph transversals via edge contractions
- The most vital nodes with respect to independent set and vertex cover
- Blockers for the stability number and the chromatic number
- Matching interdiction
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Reducing the domination number of graphs via edge contractions and vertex deletions
- Reducing graph transversals via edge contractions
- Critical edges for the assignment problem: complexity and exact resolution
- Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance
- Minimum \(d\)-transversals of maximum-weight stable sets in trees
- Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
- Complexity and algorithms for constant diameter augmentation problems
- On designing networks resilient to clique blockers
- An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance
- The complexity of blocking (semi)total dominating sets with edge contractions
This page was built for publication: Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045154)
