Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / 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). / 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).
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:10006 |
| Date | 06 February 2015 |
| Creators | Eurinardo Rodrigues Costa |
| Contributors | Rudini Menezes Sampaio, Mitre Costa Dourado, Rafael Castro de Andrade, Carlos Diego Rodrigues, Jayme Luiz Szwarcfiter, JÃlio CÃsar Silva AraÃjo |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0011 seconds