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. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:02:45Z No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-05-12T11:58:17Z (GMT) No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) / Made available in DSpace on 2016-05-12T11:58:17Z (GMT). No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) Previous issue date: 2016 / 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).

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-10-02T15:59:06Z No. of bitstreams: 1 ADEMILSON MONTES FERREIRA - DISSERTAÇÃO PPGECA 1976..pdf: 19885507 bytes, checksum: d1ca0c059c79f92f4c6eed90665dcfc4 (MD5) / Made available in DSpace on 2018-10-02T15:59:06Z (GMT). No. of bitstreams: 1 ADEMILSON MONTES FERREIRA - DISSERTAÇÃO PPGECA 1976..pdf: 19885507 bytes, checksum: d1ca0c059c79f92f4c6eed90665dcfc4 (MD5) Previous issue date: 1976-05 / Esta pesquisa de laboratório trata da influência do tempo de percolação e do nível de acidez da água nas características de permeabilidade e resistência de um solo vermelho do Estado da Paraíba. Amostras estaticamente compactadas foram submetidas a percolação de agua por diversos tempos (24,48,7 2 e 96 horas), suas permeabilidades medidas a intervalos de 12 horas e seus parâmetros de resistência triaxial no fim dos vários tempos de percolação. Três níveis de acidez da agua de percolação foram usados, 3,25, 7,3 e 12,4. Equipamento constituído de moldes e um multipermeâmetro de nível constante foi projetado e construído para o estudo, e uma nova técnica para saturação das amostras utilizadas. 0 equipamento usado mostrou resultados estatisticamente aceitáveis e seu uso tem a vantagem de diminuir o tempo de ensaio. O coeficiente de permeabilidade variou in versamente com o pH da água de percolação. Tempo de percola ção por fluxo unidirecional causou uma diminuição de permeabilidade para qualquer dos níveis de acidez investigado. Os parâmetros de resistência em termos de coesão total e efetiva e ângulo de atrito são afetados pela acidez da água de percolação. Os valores de C e f diminuem quando o pH é diminuído de 7,3 para 3,25. Aumentando o pH para 12,4 ocorre um decréscimo adicional nos valores de C e Ø' . É feita uma interpretação qualitativa deste fenômeno. Um estudo piloto limitado dos efeitos da secagem na resistência ao cisalhamento do solo Sapê-Mari mostrou que a secagem por 6 horas a 609C aumenta os valores de C e diminui Ø' para todas as condições de tempo de percolação e nível de pH. / This laboratory investigation deals with the influence of seepage time and levei of acidity of water on the permeability and strength behaviour of a red soil from the State of Paraiba. Specimens statically compacted were subjected to water percolation for varying times (24, 48, 7 2 and 96 hours), their permeabilities measured at intervals of 12 hours and their triaxial strength parameters at the end of the various percolation times. Three leveis of acidity of the seepage water were used, i.e, 3.25, 7.3 and 12.4. Equipment consisting of molds and a multipermeameter of constant head were designed and constructed for the study, and a novel technique for saturation of specimens employed. It is shown that the equipment used provides statistically aceptable results and that its use has the advantaje of shortening the time of testing. The coeficient of permeability was found to vary inversely with the pH of the seepage water. Time of seepage by unidirectional flow caused a decrease of permeability for any of the acidity leveis investigated. The strength parameters in terms of total and efective cohesion and angle of internai friction are noticeably affected by the acidity of the seepage water. The values of C and Ø' decrease slightly when the pH is lowered from 7.3 to 3.25. Increasing the pH to 12.4 causes a further decrease in the values of C and Ø'. A qualitative interpretation of this phenomena is oferred. A limited pilot study of the effects of controlled drying on the shear strength of the Sapé-Mari soil showed that drying 6 hours at 6 09C increases the values of C and decrease 4>1 for ali the conditions of time of seepage and pH levei.