Autores

5177
Erika Morais Martins Coelho
2335,6,784
5178
2335,6,784
5179
2335,6,784

Informações:

Publicações do PESC

Título
Resultados de Complexidade Relativos ao Teorema de Helly Colorido e o Número de Carathéodory
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
29/2/2012
Resumo
Nesta tese, apresentamos resultados de complexidade relativos ao Teorema de Helly colorido e ao número de Carathéodory. Motivados pelo teorema de Helly colorido para coleções de conjuntos convexos, por Lovász, definimos a propriedade de Helly colorido para uma família de hipergrafos. Descrevemos alguns fatos gerais sobre a propriedade de Helly colorido, em particular, mostramos que é Co-NP-completo decidir se uma família de p hipergrafos é Helly colorido, mesmo se p=2. No entanto, para qualquer p fixo, descrevemos um algoritmo polinomial para decidir se tal família é Helly colorido, desde que p-1 dos hipergrafos sejam p-Helly. Por outro lado, estudamos aspectos estruturais e algorítmicos sobre o número de Carathéodory considerando a convexidade P_3. Caracterizamos o número de Carathéodory de árvores, grafos bloco, grafos split e cografos. Por fim, provamos que é NP-completo decidir para um dado grafo bipartido G e um inteiro k, se o número de Carathéodory de G é pelo menos k.
Abstract
In this work, we present results on the complexity of the colorful Helly theorem and the Carathéodory number. Motivated by the colorful Helly theorem for collections of convex sets, by Lovász, we define the colorful Helly property for a family of hypergraphs. We describe some general facts about the colorful Helly property, in particular, we show that it is Co-NP-complete to decide if a family of p hypergraphs is colorful Helly, even if p = 2. However, for any fixed p, we describe a polynomial time algorithm to decide if such family is colorful Helly, provided at least p-1 of the hypergraphs are p-Helly. On the other hand, we study structural and algorithmic aspects of the Carathéodory number considering the P_3 convexity. We characterize the Carathéodory number of trees, block graphs, split graphs and cographs. Finally, we prove that it is NP-complete to decide for a given bipartite graph G and a given integer k, whether the Carathéodory number of G is at least k. 
Arquivo
Topo