Defesa de Dissertação de Mestrado: Aluno Eurinardo Rodrigues Costa
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)