.png)
.png)
Accessibility Tools
Os Seminários PESC têm como objetivo trazer palestras acessíveis a um público mais amplo, ministradas por pesquisadores e professores mais experientes (tanto do PESC como de instituições externas). Ao longo do ano, teremos temas e focos variados, podendo ser mais específicos ou mais abrangentes.
A apresentação e discussão de ideias novas e antigas de diferentes temas contribui de maneira fundamental para a formação e pesquisa desenvolvida por alunos e professores, sendo muitas vezes de interesse de um público mais amplo.
Os Seminários que são on-line ou híbridos ficam gravados no Canal do PESC no YouTube, que apresenta muitas outras gravações importantes sobre o que acontece no PESC.
On Edge Domination of Graphs
Jayme Luiz Szwarcfiter
Dia 17/05 (quarta-feira), 10 horas, Sala H-324B.
Abstract:
Denote by G, an undirected simple graph, with vertex set V , and edge set E. An edge e ∈ E dominates itself and every edge adjacent to e. A set E′ ⊆ E is an (edge) dominating set of G, if each edge of E is dominated by some edge of E' . The domination is called efficient if each edge is dominated exactly once, and is called proper if each edge of E \ E′ is dominated exactly once. In this talk, we survey and describe complexity results on these three types of edge domination. In particular, we consider the class of graphs, where each edge is contained in some triangle. We mention hardness and polynomial time cases on subclasses of this class, for edge domination problems.
Short Bio:
Jayme Luiz Szwarcfiter é Professor Emérito da UFRJ atuando no Programa de Engenharia de Sistemas e Computação da COPPE, no Instituto de Matemática e no Núcleo de Computação Eletrônica. Atualmente é Pesquisador Visitante do Instituto de Matemática e Estatística da UERJ. Atua nas áreas de Algoritmos, Teoria da Computação e Matemática Discreta. Publicou diversos livros-textos influentes nessas áreas, além da formação de dezenas de mestres e doutores. É Pesquisador 1-A do CNPq, Membro Titular da Academia Brasileira de Ciências, Grã-Cruz da Ordem Nacional do Mérito Científico, e recebeu inúmeros prêmios de destaque nacional e internacional por suas contribuições acadêmicas e científicas.
