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.
 Complexidade e Estrutura: a aparente facilidade dos grafos-(k,l) bem cobertosSulamita Klein, Professor Titular, IM-COPPE/UFRJ 28 de junho (quarta), 11h Um grafo G = (V, E) é bem coberto quando todos os seus conjuntos independentes maximais têm o mesmo número de vértices. Chvátal e Slater mostraram que o reconhecimento de grafos bem cobertos em geral é coNP-completo. Entretanto, existem reconhecimentos polinomiais para algumas classes de grafos: bipartidos, split, cografos entre outras. Uma propriedade algoritmica interessante dos grafos bem cobertos é que o algoritmo guloso usado para encontrar um conjunto independente maximal sempre produz um conjunto independente máximo quando aplicado em um grafo bem coberto. G = (V, E) é um grafo-(k, l) se o seu conjunto de vértices V pode ser particionado em k conjuntos independentes e l cliques. Essa classe de grafos engloba diversos grafos conhecidos. Brandstädt provou que o reconhecimento de grafos-(k, l) é polinomial para k <= 2 e l <= 2 e NP-completo caso contrário. Nessa palestra vamos considerar grafos que são bem cobertos e ao mesmo tempo são grafos-(k, l) e discutir a complexidade do problema de decisão GRAFO-(k, l) BEM-COBERTO, que tem como entrada um grafo G = (V, E) e a questão: G é (k, l) e bem-coberto? Esse trabalho foi feito em colaboração com Luerbio Faria (UERJ) e Sancrey Rodrigues Alves (FAETEC-atualmente aluno de doutorado do PESC).
Biografia resumida Sulamita Klein é doutora pelo Programa de Engenharia de Sistemas e Computação da COPPE desde 1994, tendo sido orientada pelo Professor Jayme Szwarcfiter. Fez pós-doutorado em 2000 na Universidade Pierre e Marie Curie(Paris VI). Sua carreira docente transcorreu na UFRJ, onde ingressou no Instituto de Matemática em 1979 e na COPPE/Sistemas em 1995. Atualmente é professora titular da UFRJ. É bolsista de produtividade do CNPq desde 1995, sendo atualmente pesquisadora 1B do CNPq. É Cientista do nosso Estado (FAPERJ) desde 2007. Atua nas áreas de Teoria dos Grafos e Complexidade. |
.png)
.png)
