Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term

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

Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010), Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term, Discrete Mathematics, 310, 1, p. 132-146. http://dx.doi.org/10.1016/j.disc.2009.08.009

Type

Article accepté pour publication ou publié

Date

2010

Journal name

Discrete Mathematics

Volume

310

Number

Publisher

Elsevier

Pages

132-146

Abstract (EN)

Given an undirected previous termgraphnext term G=(V,E) with matching number ν(G), previous termanext term d-previous termblocker is anext term subset of edges B such that ν((V,Eset minusB))≤ν(G)−d and previous termanext term d-previous termtransversalnext term T is previous termanext term subset of edges such that every maximum matching M has |M∩T|≥d. While the associated decision problem is NP-complete in previous termbipartite graphsnext term we show how to construct efficiently minimum d-previous termtransversalsnext term and minimum d-previous termblockersnext term in the special cases where G is previous terma grid graph or anext term tree.

Subjects / Keywords

Caterpillar; Tree; Grid graph; Blocker; Transversal; Matching