Autores

5921
2340,413,414
5922
2340,413,414
5923
2340,413,414

Informações:

Publicações do PESC

Título
Complexidade dos Problemas Sanduíche e Probe para Subclasses de Grafos-(k,l)
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
17/2/2016
Resumo
Neste trabalho apresentamos uma caracterização estrutural e decomposição para cografos-(2,1) e (1,2). Além disso, apresentamos resultados concernentes a dicotomia P versus NP-completo da complexidade computacional do problema sanduíche para grafos cordais-(k,l) e fortemente cordais-(k,l). Especificamente, mostramos que para grafos fortemente cordais-(k,l), o problema sanduíche é NP-completo para k >= 1 e l >= 1, fixos, bem como para k=0 e l >= 3, fixo. Para grafos cordais-(k,l), provamos que o problema é NP-completo para k + l >= 3, com k e l inteiros positivos fixos e para k = 0 e l >= 3, fixo.  Ainda sobre problemas sanduíche e como uma aplicação da caracterização para cografos-(2,1) e (1,2), mostramos que, embora o problema sanduíche para grafos de limiar seja polinomial, o problema sanduíche para a junção de dois grafos de limiar é NP-completo. Através desse resultado, conseguimos classificar completamente a dicotomia P versus NP-completo da complexidade computacional do problema sanduíche para cografos-(k,l). Introduzimos o conceito de problemas sanduíche com condições de contorno e apresentamos alguns resultados polinomiais para algumas classes para as quais o problema sanduíche na versão original é NP-completo. No âmbito de problemas probe, analisamos a complexidade dos problemas probe particionado junção de dois grafos de limiar e ambas as versões probe para cografo-(2,1) e (1,2). Obtivemos algoritmos em tempo polinomial para os mesmos. Além disso, trabalhamos com classes de grafo definidas por subgrafos proibidos, estudo este que nos conduziu a um resultado interessante que relaciona a Conjectura para Grafos Probe Perfeitos com a Conjectura Forte para Grafos Probe Perfeitos e com o mais famoso problema em aberto para problemas sanduíche: o problema sanduíche para grafos perfeitos.
Abstract
In this work we present a structural characterization and decomposition for cographs-(2,1) and (1,2). Moreover, we present results concerning the P versus NP-complete dichotomy of  chordal-(k,l) and strongly chordal-(k,l) graph sandwich problems computational complexity . Specifically, we show that, for strongly chordal-(k,l), the graph sandwich problem is NP-complete for k >= 1 and l >= 1, fixed, as well as for k=0 and l >= 3, fixed. For chordal-(k,l) graphs, we prove that the problem is NP-complete for k + l >= 3, with k and l positive fixed integers and for k = 0 and l >= 3, fixed.  Still about graph sandwich problems and as an application of the characterization for cographs-(2,1) and (1,2), we show that, although we can solve threshold graph sandwich problem in polynomial time, join of two threshold graph sandwich problem is NP-complete. With this result, we could fully classify the P versus NP-complete dichotomy of cograph-(k,l) graph sandwich problem computational complexity. We introduced the concept of graph sandwich problems with boundary conditions and we show some polynomial time results for some classes for which graph sandwich problem is NP-complete. Under probe problems, we analyze partitioned probe join of two threshold  and both probe versions for cograph-(2,1) and (1,2) complexities. We present polynomial time algorithms for these problems. Furthermore, we deal with graph classes defined by forbidden subgraphs and this study lead us to an interesting result that relates the Probe Perfect Graph Conjecture with Strong Probe Perfect Graph Conjecture and with the most famous open graph sandwich problem: perfect graph sandwich problem. 
Arquivo
Topo