O Ciclo de Seminários PESC volta a acontecer com uma palestra da prof. Sulamita Klein, do PESC.

Sula irá apresentar trabalhos recentes em uma classe de grafos que fazem problemas tradicionalmente difíceis ficarem mais fáceis. É um bom exemplo de como estrutura afeta funcionalidade! A palestra promete ser acessível, sem que seja necessário conhecimento prévio do tema.

Programe-se, participe, e ajude na divulgação! 

Mais detalhes abaixo ou clicando aqui.

-------

Palestrante:

Sulamita Klein, Professor Titular, IM-COPPE/UFRJ

Título:

Complexidade e Estrutura: a aparente facilidade dos grafos-(k,l) bem cobertos

Dia/horário/local:

Quarta, 28 de junho, 11h, sala H-324B

Resumo:

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).

Bio 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.