Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Os 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 P4-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_4-Esparsos e P_4-Laden. / The 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 P4-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 P4-Sparse and
P4-Laden graphs.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:6454 |
| Date | 22 February 2013 |
| Creators | Nicolas de Almeida Martins |
| Contributors | Rudini Menezes Sampaio, Ana Shirley Ferreira da Silva, Victor Almeida Campos |
| 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 | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| 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.0018 seconds