Título: Convexidade Monofônica em Classes de Grafos

Data: 06/02/2015 Horário: 16h Local: Sala de Seminários Bloco 952

Resumo: Neste trabalho, estudamos alguns parâmetros para a convexidade monofônica em classes de grafos e apresentamos nossos resultados acerca do assunto. Provamos que decidir se o número de m-intervalo é no máximo 2 e decidir se o tempo de m-percolação é no máximo 1 são problemas NP-completos mesmo em grafos bipartidos. Também provamos que o número de m-convexidade é tão difícil de aproximar quanto o problema da Clique Máxima, que é, para cada ε > 0, O()-inaproximável em tempo polinomial, a menos que P=NP. Finalmente, apresentamos um algoritmo de tempo polinomial para determinar o número de m-convexidade em classes hereditárias de grafos onde a computação do tamanho da clique máxima é em tempo polinomial (como grafos perfeitos e grafos planares).

Banca:

• RUDINI MENEZES SAMPAIO (UFC – Orientador)
• MITRE COSTA DOURADO  (UFRJ - Coorientador)
• RAFAEL CASTRO DE ANDRADE  (UFC)
• CARLOS DIEGO RODRIGUES (UFC)
• JULIO CESAR SILVA ARAUJO  (UFC)
• JAYME LUIZ SZWARCFITER  (UFRJ)