Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorSampaio, Rudini Menezes-
dc.contributor.authorCosta, Eurinardo Rodrigues-
dc.identifier.citationCOSTA, 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.pt_BR
dc.description.abstractIn 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).pt_BR
dc.subjectCiência da computaçãopt_BR
dc.subjectConvexidade monofônicapt_BR
dc.subjectGrafos bipartidospt_BR
dc.subjectNúmero de convexidadept_BR
dc.subjectTempo de percolaçãopt_BR
dc.titleConvexidade monofônica em classes de grafospt_BR
dc.typeDissertaçãopt_BR, Mitre Costa-
dc.description.abstract-ptbrNeste 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).pt_BR
dc.title.enMonophonic convexity in classes of graphspt_BR
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2016_dis_ercosta.pdf1,57 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.