MinistÃre de l'Enseignement SupÃrieur et de la Recherche / 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 definiÃÃ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 definiÃÃ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. / 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
definition 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 definition 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:5817 |
| Date | 13 September 2012 |
| Creators | JÃlio CÃsar Silva AraÃjo |
| Contributors | ClÃudia Linhares Sales, Jean-Claude Bermond, FrÃdÃric Giroire, Ricardo Cordeiro CorrÃa, Christophe Paul, FrÃdÃric Maffray |
| 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 | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| 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.0129 seconds