|
 
|
[ZRP09] Blockers and Transversals
Revue Internationale avec comité de lecture : Journal Discrete Mathematics, vol. 309(13), pp. 4306-4314, 2009, (doi:10.1016/j.disc.2009.01.006)
motcle:
Résumé:
We explore connections between d-blockers B in a graph G = (V;E) (i.e.
subsets of edges whose removal decreases by at least d the cardinality of
maximum matchings) and d-transversals T (i.e. subsets of edges such that
every maximum matching M has at least d edges in
T. Special classes of graphs
are examined which include complete graphs, regular bipartite graphs, grid
graphs, chains and cycles. We also study the complexity status of finding
minimum transversals and blockers. Algorithms for d-transversals and d-
blockers based on dynamic programming are given for trees.
Equipe:
oc
Collaboration:
LAMSADE
BibTeX
| @article { | |||
| ZRP09, | |||
| title | = | "{Blockers and Transversals}", | |
| author | = | "R. Zenklusen and B. Ries and C. Picouleau and D. de Werra and M.-C. Costa and C. Bentz", | |
| journal | = | "Discrete Mathematics", | |
| year | = | 2009, | |
| volume | = | 309, | |
| number | = | 13, | |
| pages | = | "4306-4314", | |
| doi | = | "10.1016/j.disc.2009.01.006", | |
| } | |||
