A Convexidade P3 para Grafos não Direcionados
Autores
|
5278 |
Carmen Cecilia Centeno
|
2386,6,2018
|
|
5279 |
2386,6,2018
|
|
|
5280 |
2386,6,2018
|
Informações:
Publicações do PESC
Título
A Convexidade P3 para Grafos não Direcionados
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
15/8/2012
Resumo
Apresenta-se, nesta tese, um estudo sobre três parâmetros da convexidade P3,sendo eles: número de convexidade P3, número P3 e número de envoltória P3. Provamos que tais problemas são NP-completos para a classe de grafos gerais. Para as classes de árvores, cografos e certas grades mostramos que os problemas podem ser resolvidos em tempo polinomial. Trabalhamos também com a classe dos cordais,para a qual obtivemos uma redução para os problemas de número P3 e número de convexidade P3, já para o número de envoltória P3 desenvolvemos um algoritmo de tempo polinomial. Por fim, consideramos a classe de grafos na qual o número P3 é igual ao número de envoltória P3, para esta desenvolvemos um algoritmo de reconhecimento considerando os grafos livres de triângulos.
Abstract
In this work, we present a study about three convexity P3 parameters, named: P3 convexity number, P3 number and P3 hull number. We prove that all these problems are NP-complete for graphs in general. For the classes of trees, cographs and certain grid graphs we give polynomial time solution. We have also considered the chordal graphs, for which we describe reductions for the P3 number and the P3 convexity number problems, but for the P3 hull number we developed a polynomial time algorithm. Finally, we consider the class of graphs which has P3 number equal P3 hull number, for this class we developed a recognizing algorithm that consider the triangle free graphs.
Arquivo