Esta tesis trata sobre un problema de reconstrucción en Tomografía Discreta en el cual se está interesado en colorear una grilla usando k colores, de tal forma que para cada fila y columna, el número de celdas de cada color sea un cierto valor previamente dado. Para k = 2, un resultado clásico de la Combinatoria entrega una condición necesaria y suficiente para la existencia de tal coloración junto con un algoritmo polinomial para construirla cuando existe. Por otro lado, Chrobak y Dürr mostraron que para k mayor o igual a 4 el problema es NP-difícil. La equivalencia natural entre una grilla y un grafo bipartito completo muestra que el caso k=3 corresponde a la restricción a esta clase de grafos del siguiente problema: Dados un grafo G y funciones enteras b¹ y b² en V(G), ¿existen b¹ y b²-factores de G que sean disjuntos? En esta tesis introducimos una nueva condición para este problema, la que resulta ser suficiente cuando G es un grafo bipartito completo y la diferencia entre el máximo y mínimo valor de b¹ + b² es a los más dos. La demostración de este resultado se basa en un algoritmo polinomial que encuentra dos factores disjuntos o bien un certificado de inexistencia. Junto con esto, la contribución principal de esta tesis es la prueba de NP-dificultad del problema para grafos bipartitos completos cuando no se impone ninguna condición a b¹ y b². Esto resuelve el caso k = 3 del mencionado problema en Tomografía Discreta, lo que cierra el problema para todos los valores de k. Como corolario obtenemos además que el problema para grafos completos es también NP-difícil. Para el problema de unicidad, caracterizamos las transformaciones que preservan las funciones b¹ y b² cuando G es un grafo bipartito. Este resultado es luego utilizado para probar la existencia de invariantes para algunas 3-coloraciones de la grilla. Además, estudiamos la generalización del problema de k-coloración a la reconstrucción de embaldosados de la grilla usando como baldosas k rectángulos de diferentes tamaños. Para este problema, presentamos demostraciones que abarcan y extienden todos los resultados previos conocidos. Para finalizar, se prueba la existencia de un núcleo cuadrático para una generalización del problema de Vertex Cover parametrizado por el tamaño requerido del conjunto solución.

Submitted by Maike Costa (maiksebas@gmail.com) on 2017-06-29T14:15:20Z No. of bitstreams: 1 arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5) / Made available in DSpace on 2017-06-29T14:15:20Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5) Previous issue date: 2017-01-31 / The Maximu m Diversity Problem (MDP) is a problem of combinatorial optimization area that aims to select a pre-set number of elements in a given set so that a sum of the differences between the selected elements are greater as possible. MDP belongs to the class of NP-Hard problems, that is, there is no known algorithm that solves in polynomial time accurately. Because they have a complexity of exponential order, require efficient heuristics to provide satisfactory results in acceptable time. However, heuristics do not guarantee the optimality of the solution found. This paper proposes a new hybrid approach for a resolution of the Maximum Diversity Problem and is based on the Particle Swarm Optimization (PSO) and Tabu Search (TS) metaheuristics, The algorithm is called PSO_TS. The use of PSO_TS achieves the best results for known instances testing in the literature, thus demonstrating be competitive with the best algorithms in terms of quality of the solutions. / O Problema da Diversidade Máxima (MDP) é um problema da área de Otimização Combinatória que tem por objetivo selecionar um número pré-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possível. O MDP pertence a classe de problemas NP-difícil, isto é, não existe algoritmo conhecido que o resolva de forma exata em tempo polinomial. Por apresentarem uma complexidade de ordem exponencial, exigem heurísticas eficientes que forneçam resultados satisfatórios em tempos aceitáveis. Entretanto, as heurísticas não garantem otimalidade da solução encontrada. Este trabalho propõe uma nova abordagem híbrida para a resolução do Problema da Diversidade Máxima e está baseada nas meta-heurísticas de Otimização por Nuvem de Partículas (PSO) e Busca Tabu(TS). O algoritmo foi denominado PSO_TS. Para a validação do método, os resultados encontrados são comparados com os melhores existentes na literatura.