voltarData: 31/05/2017
Título: Eliminating All Cycles by Removing a Matching
Palestrante: Carlos Vinícius G. C. Lima, UFF.
Data: 31 de maio de 2017, 13h.
Local: Sala 409, Bloco H, IME, Campus Gragoatá, UFF.
Resumo: The problem of destroying all cycles by removing vertices or edges is classical in the literature. However, despite the large number of different works on this theme, yet there remains quite a wide field to be explored in the study of this problem when restrictions on the set of removed vertices or edges are required.
We study the problem of destroying all cycles by removing a matching. We show that it is NP-complete determining whether a graph admits such a removal even for subcubic graphs with exactly two vertices of degree two. We also present polynomial time algorithms for some classical classes, that are (claw, paw)-free graphs, P_5-free graphs, chordal graphs, and C_4-free distance hereditary graphs.
Obs: Trabalho em conjunto com Uéverton S. Souza (UFF) e Dieter Rautenbach (Ulm University). O palestrante atualmente é Pós-doutorando na Pós-graduação da Matemática - IME UFF - com bolsa CAPES-projeto coordenado profa. Simone Dantas
Confira aqui a apresentação