Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/18951
Título: Coloração em convexidade em grafos
Título em inglês: Graph Coloring and Graph Convexity
Autor(es): Araújo, Júlio César Silva
Orientador(es): Sales, Cláudia Linhares
Coorientador(es): Giroire, Frédéric
Bermond, Jean-Claude
Palavras-chave: Ciência da computação
Teoria de Grafos
Complexidade Computacional
Coloração
Convexidade
Graph Theory
Data do documento: 2012
Citação: ARAÚJO, J. C. S. (2012)
Resumo: Nesta 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.
Abstract: In 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.
Descrição: ARAÚ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.
URI: http://www.repositorio.ufc.br/handle/riufc/18951
Aparece nas coleções:DCOMP - Teses defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2012_tese_jcsaraujo.pdf2,1 MBAdobe PDFVisualizar/Abrir


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