Journal article

Blockers and transversals in some subclasses of bipartite graphs : When caterpillars are dancing on a grid

Show more…
    2010
Published in:
  • Discrete Mathematics. - 2010, vol. 310, p. 132-146
English Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))<=\nu(G)-d and a d-transversal T is a subset of edges such that every maximum matching M has |M \cap T|>= d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/308018
Statistics

Document views: 6 File downloads:
  • blockersandtransversalsii.pdf: 7