\(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs

DOI10.1016/j.jda.2012.06.002zbMath1268.05192OpenAlexW4298220245MaRDI QIDQ2376794

Cédric Bentz, Dominique de Werra, Marie-Christine Costa, Bernard Ries, Christophe Picouleau

Publication date: 24 June 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.06.002

zbMATH Keywords

matchingpolynomial time algorithmnetwork flowvertex covermaximum weight stable setweighted bipartite graphminimum total costminimum d-transversalminimum weight vertex

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Reducing the chromatic number by vertex or edge deletions ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Blockers for the stability number and the chromatic number ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs

Cites Work

• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Blockers and transversals
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Crown reductions for the minimum weighted vertex cover problem
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)

This page was built for publication: \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs