Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/16736
Título: Convexidade Monofônica em Classes de Grafos
Título em inglês: Monophonic convexity in classes of graphs
Autor(es): Costa, Eurinardo Rodrigues
Orientador(es): Sampaio, Rudini Menezes
Coorientador(es): Dourado, Mitre Costa
Palavras-chave: Ciência da computação
Convexidade monofônica
Grafos bipartidos
NP-completude, Inaproximabilidade
Número de convexidade
Tempo de percolação
Data do documento: 2016
Citação: COSTA, E. R.
Resumo: Neste trabalho, estudamos alguns parâmetros para a convexidade monofônica em algumas 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 é, $O(n^{1-varepsilon})$-inaproximável em tempo polinomial, a menos que P=NP, para cada $varepsilon>0$. 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).
Abstract: In this work, we study some parameters of monophonic convexity in some classes of graphs and we present our results about this subject. We prove that decide if the $m$-interval number is at most 2 and decide if the $m$-percolation time is at most 1 are NP-complete problems even on bipartite graphs. We also prove that the $m$-convexity number is as hard to approximate as the maximum clique problem, which is, $O(n^{1-varepsilon})$-unapproachable in polynomial-time, unless P=NP, for each $varepsilon>0$. Finally, we obtain polynomial time algorithms to compute the $m$-convexity number on hereditary graph classes such that the computation of the clique number is polynomial-time solvable (e.g. perfect graphs and planar graphs).
Descrição: COSTA, Eurinardo Rodrigues. Convexidade Monofônica em Classes de Grafos. 2016. 54 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016.
URI: http://www.repositorio.ufc.br/handle/riufc/16736
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2016_dis_ercosta.pdf1,57 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.