Minimum \(d\)-blockers and \(d\)-transversals in graphs

DOI10.1007/s10878-010-9334-6zbMath1263.90110OpenAlexW2086790666MaRDI QIDQ411244

Marie-Christine Costa, Christophe Picouleau, Dominique de Werra

Publication date: 4 April 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9334-6

zbMATH Keywords

bipartite graphsplit graphstable settransversalcoverbilevel programming\(s\)-\(t\) cut\(s\)-\(t\) pathblocker

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (21)

\(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs ⋮ Reducing the chromatic number by vertex or edge deletions ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ Assistance and interdiction problems on interval graphs ⋮ Reducing the vertex cover number via edge contractions ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ 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 vertices and edges in \(H\)-free graphs ⋮ Blockers for the stability number and the chromatic number ⋮ Blocking optimal structures ⋮ Unnamed Item ⋮ 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 ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Safety in \(s\)-\(t\) paths, trails and walks

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• The node-deletion problem for hereditary properties is NP-complete
• A constructive characterization of trees with at least k disjoint maximum matchings
• Foundations of bilevel programming
• On the number of vertices belonging to all maximum stable sets of a graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Discrete linear bilevel programming problem
• An overview of bilevel optimization
• NP-completeness results for edge modification problems
• Edge-Deletion Problems
• Node-Deletion Problems on Bipartite Graphs
• The structure and maximum number of maximum independent sets in trees
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Disjoint (s, t)‐cuts in a network

This page was built for publication: Minimum \(d\)-blockers and \(d\)-transversals in graphs