Idioma:

Blockers and transversals

Zenklusen, R. ; Ries, B. ; Picouleau, C. ; de Werra, D. ; Costa, M.-C. ; Bentz, C.

Discrete mathematics, 2009-07, Vol.309 (13), p.4306-4314 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Blockers and transversals
Autor: Zenklusen, R. ; Ries, B. ; Picouleau, C. ; de Werra, D. ; Costa, M.-C. ; Bentz, C.
Assuntos: Applied sciences ; Blocker ; Complete bipartite graph ; Complete graph ; Computer science; control theory; systems ; Exact sciences and technology ; Information retrieval. Graph ; Matching ; Theoretical computing ; Transversal
É parte de: Discrete mathematics, 2009-07, Vol.309 (13), p.4306-4314
Descrição: Given an undirected graph G = ( V , E ) with matching number ν ( G ) , we define d -blockers as subsets of edges B such that ν ( ( V , E ∖ B ) ) ≤ ν ( G ) − d . We define d -transversals T as subsets of edges such that every maximum matching M has | M ∩ T | ≥ d . We explore connections between d -blockers and d -transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d -transversals and d -blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs.
Editor: Kidlington: Elsevier B.V
Idioma: Inglês

Links

Voltar para lista de resultados