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

DOI10.1016/J.JDA.2012.06.002MaRDI QIDQ2376794zbMATH OpenOpenAlexFDO

Authors Cédric Bentz, Marie-Christine Costa, Bernard Ries, Dominique De Werra, 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

matchingmaximum weight stable setminimum d-transversalminimum total costminimum weight vertexnetwork flowpolynomial time algorithmvertex coverweighted bipartite graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4075093
• Minimum d-transversals of maximum-weight stable sets in trees
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• On a class of vertex-transitive distance-regular covers of complete graphs
• Maximum \(k\)-covering of weighted transitive graphs with applications
• Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph
• On the minimum vertex covering transversal dominating sets in graphs and their classification
• On vertex stability with regard to complete bipartite subgraphs
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• scientific article; zbMATH DE number 2068132

Cites work

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

Cited in

(8)

• Blockers and transversals
• Critical vertices and edges in \(H\)-free graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Reducing the chromatic number by vertex or edge deletions
• Minimum d-transversals of maximum-weight stable sets in trees
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Blockers for the stability number and the chromatic number
• On blockers and transversals of maximum independent sets in co-comparability graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376794)