Journal article

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

Show more…
Published in:
  • Journal of Discrete Algorithms. - Elsevier. - 2012, vol. 17, p. 95-102
English Let G = (V , E) be a graph in which every vertex v ∈ V has a weight w(v)>=0 and a cost c(v) >=0. Let SG be the family of all maximum-weight stable sets in G. For any integer d 0, a minimum d-transversal in the graph G with respect to SG is a subset of vertices T ⊆ V of minimum total cost such that |T ∩ S| d for every S ∈ SG. In this paper, we present a polynomial-time algorithm to determine minimum d-transversals in bipartite graphs. Our algorithm is based on a characterization of maximum-weight stable sets in bipartite graphs. We also derive results on minimum d-transversals of minimum-weight vertex covers in weighted bipartite graphs.
Faculté des sciences économiques et sociales et du management
Département d'informatique
  • English
Computer science and technology
License undefined
Persistent URL

Document views: 28 File downloads:
  • transversals.pdf: 59