Partições em Grafos: Caracterizações, Algoritmos e Complexidade
Autores
|
2153 |
257,427
|
|
|
2154 |
257,427
|
Informações:
Publicações do PESC
Esta tese considera três problemas de partições em gratos e propõe caracterizações, algoritmos e classificações segundo a complexidade computacional. Consideramos uma generalização do problema de coloração clássica: o problema de coloração por listas. Gravier provou uma versão para coloração por listas do Teorema de Nordhaus-Gaddum e Zsolt Tuza, propôs o seguinte problema: quais grafos satisfazem a igualdade na versão coloração por listas do teorema de Nordhaus-Gaddum? Em nosso trabalho, respondemos a esta questão caracterizando tais grafos. Estudamos a complexidade do Problema Grafo Sanduíche (k.l). Provamos que o Problema Grafo Sanduíche (k,l) é NP-completo para os casos k = 1 e l = 2; k = 2 e l = 1; ou k = l = 2. Isto classifica completamente a complexidade do Problema Grafo Sanduíche (k,l) como segue: o problema é NP-completo, se k / l > 2; o problema é polinomial caso contrário. Além disso, provamos que o problema é polinomial se limitamos o grau máximo e os valores para k, l são: k = 1 e l = 2; ou k = 2 e l = 1. Estudamos o conceito de H-partição. Neste estudo, analisamos todos os problemas de partição de vértices em quatro partes não-vazias com somente restrições externas de acordo com a estrutura de um grafo modelo H. Além disso, apresentamos uma solução parcial para este Problema de H-partição.
This thesis considers three graph partition problems and proposes characterizations, algorithms and computational complexity classifications. We consider a generalization of the classical colouring problem: the list colouring probtem. Gravier proved a list colouring version of the Nordhaus-Gaddum theorem. Zsolt Tuza proposed the following problem: which graphs satisfy the equality in the list colouring version of the Nordhaus-Gaddum theorem? We answer this question by characterizing these graphs. We study the complexity of the (k.l) Graph Sandwich Problem. We prove that the (k,l)-Graph Sandwich Problem is NP-complete for the cases k = 1 and l =2; k = 2 and l = 1; or k = l = 2. This completely classifies the complexity of the (k,l)-Graph Sandwich Problem as follows the problem is NP-complete, if k / l > 2: the problem is polynomial otherwise. In addition. we prove that the problem is polynomial if we bound the maximum degree and the values for k,l are: k = l and l = 2; or k = 2 and l = 1. We study the concept of H-partition. We analise all vertex partition problems into four non-empty parts according to external restrictions with respect to the structure of a model graph H. We present a partial solution for this H-partition problem.