Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorSales, Cláudia Linhares-
dc.contributor.authorAraújo, Júlio César Silva-
dc.identifier.citationARAÚJO, Júlio César Silva. Coloração em convexidade em grafos. 2012. 207 f. Tese (Mestrado em ciência da computação) - Universidade Federal do Ceará, Fortaleza-CE, 2012.pt_BR
dc.description.abstractIn this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de finition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de finition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.pt_BR
dc.subjectCiência da computaçãopt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectComplexidade computacionalpt_BR
dc.subjectGraph theorypt_BR
dc.titleColoração em convexidade em grafospt_BR
dc.typeTesept_BR, Frédéric-, Jean-Claude-
dc.description.abstract-ptbrNesta tese, estudamos vários problemas de teoria dos grafos relativos à coloração e convexidade em grafos. A maioria dos resultados contidos aqui são ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloração de grafos que é uma das áreas mais importantes de teoria dos grafos. Primeiro, consideramos três problemas de coloração chamados coloração gulosa, coloração ponderada e coloração ponderada imprópria. Em seguida, discutimos um problema de decisão, chamado boa rotulagem de arestas, cuja de finição foi motivada pelo problema de atribuição de frequências em redes óticas. A segunda parte desta tese é dedicada a um parâmetro de otimização em grafos chamado de número de fecho (geodético). A de finição deste parâmetro é motivada pela extensão das noções de conjuntos e fecho convexos no espaço Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuído.pt_BR
dc.title.enGraph Coloring and Graph Convexitypt_BR
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2012_tese_jcsaraujo.pdf2,1 MBAdobe PDFView/Open

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