Cortes-Estrela e Cortes-Clique Sanduíche
Autores
|
2308 |
257,983
|
|
|
2309 |
257,983
|
Informações:
Publicações do PESC
Este trabalho descreve um estudo sobre problemas sanduíche. Problemas sanduíche são generalizações de problemas de reconhecimento de uma propriedade II. Enquanto em problemas de reconhecimento comum existe apenas um grafo como entrada, em problemas sanduíche existem dois grafos e procura-se por um terceiro grafo, intermediário entre os dois grafos de entrada, satisfazendo a propriedade II. Apresentamos dois resultados originais sobre propriedades cujo reconhecimento é polinomial: corte-estrela e corte-clique. Mostramos que esses problemas despertam interesse para serem estudados em sua forma sanduíche. Propomos um algoritmo polinomial de complexidade O(n3) para o problema sanduíche para corte-estrela, fazendo algumas modificações num algoritmo conhecido simples de reconhecimento. Por fim, propomos uma prova de NP-completude, reduzindo o problema 1-em-3 3Sat (sem literais negativos) para o problema sanduíche para corte-clique, notando a relação deste problema com o reconhecimento de corte estável, problema já conhecido NP-completo.
This work describes a study on graph sandwich problems. Sandwich problems generalize graph recognition problems with respect to a property ?. A recognition problem has a graph as input, whereas a sandwich problem has two graphs as input. In a sandwich problem, we look for a third graph, whose edge set lies between the edge sets of two given graphs. This third graph is required to satisfy a property II. We present two original sandwich results corresponding to two known polynomial recognition problems: star cutset and clique cutset. We show these two graph decomposition problems are of interest with respect to sandwich problems. We propose a polynomial algorithm of O(n3)-time for star cutset sandwich problem. We propose an NP-completeness transformation from 1-in-3 3SAT (with no negative literals) to clique cutset sandwich problem.