Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/18505
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorSampaio, Rudini Menezes-
dc.contributor.authorMartins, Nicolas de Almeida-
dc.date.accessioned2016-07-20T12:11:19Z-
dc.date.available2016-07-20T12:11:19Z-
dc.date.issued2013-
dc.identifier.citationMARTINS, Nicolas de Almeida. Problemas de coloração de grafos com poucos P4´s. 2013. 53 f. Dissertação (Mestrado em ciência da computação) - Universidade Federal do Ceará, Fortaleza-CE, 2013.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/18505-
dc.description.abstractThe coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q-4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P₄-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q-4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P₄-Sparse and P₄-Laden graphs.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectCiência da computaçãopt_BR
dc.subjectL(2,1)-Coloraçãopt_BR
dc.subjectRepresentações dos grafospt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectAlgorítmospt_BR
dc.subjectGrafos (q,q−4)pt_BR
dc.subjectColoração harmônicapt_BR
dc.subjectDecomposição primevalpt_BR
dc.subjectM-Partiçãopt_BR
dc.titleProblemas de coloração de grafos com poucos P4´spt_BR
dc.typeDissertaçãopt_BR
dc.contributor.co-advisorSilva, Ana Shirley Ferreira da-
dc.description.abstract-ptbrOs problemas de coloração estão entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teórica e prática. O problema da L(2,1)-coloração, por exemplo, pode ser aplicado na atribuição de frequências de rádio a torres de transmissão visando a diminuição de interferências nas transmissões. No entanto a maior parte das colorações de Grafos é de difícil resolução(NP-Difíceis). Nesta dissertação, estudamos os problemas de L(2,1)-coloração, coloração harmônica e M-partição. Tendo em vista que os problemas de coloração abordados nesta dissertação são todos NP-difíceis, decidimos estudar as restrições destes problemas a (q,q-4)-grafos , com q fixo. As soluções utilizam a decomposição primeval destes grafos. Ressaltamos ainda que esta classe contém os cografos e os grafos P₄-esparsos. Os algoritmos encontrados desta maneira são chamados de Fixed Parameter Tractable(FPT), pois são polinomiais quando consideramos um determinado parâmetro como um valor fixo. Além da obtenção de algoritmos para diversos problemas de coloração restritos aos (q,q-4)-grafos, com q fixo, também avaliamos a Conjectura de Griggs-Yeh com relação aos grafos P₄ -Esparsos e P₄-Laden.pt_BR
dc.title.enColoring problem of graphs with few P4'spt_BR
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2013_dis_namartins.pdf503,25 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


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