Problemas Sanduíche para grafos-(2,1) com Condições de Contorno
Autores
|
5192 |
2340,413
|
|
|
5193 |
2340,413
|
Informações:
Publicações do PESC
Título
Problemas Sanduíche para grafos-(2,1) com Condições de Contorno
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
29/2/2012
Resumo
Esta dissertação apresenta uma nova proposta de trabalho com relação aos problemas sanduíche. Este tipo de problema, em sua forma original, foi introduzido em 1995 por Golumbic, Kaplan e Shamir e pode ser definido da seguinte maneira: Dados dois grafos G1 = (V,E1) e G2 = (V,E2) tais que E1 está contido em E2, existe um grafo G = (V,E) tal que E1 está contido em E que, por sua vez, está contido em E2 e G satisfaz uma dada propriedade P?
O foco deste trabalho são problemas sanduíche aos quais atribuímos propriedades específicas aos seus grafos de entrada, que chamamos de condições de contorno. A estes "problemas sanduíche generalizados" demos o nome de problemas sanduíche com condições de contorno. Nosso objetivo consiste em tentar transformar problemas conhecidos e que têm solução difícil em problemas mais maleáveis e possivelmente solucionáveis em tempo polinomial. Trabalhamos com quatro problemas que não haviam sido estudados: problema sanduíche para grafos fortemente cordais-(2,1) e três problemas sanduíche para grafos-(2,1) com condições de contorno, a saber: problema sanduíche para grafos-(2,1) com G1 e G2 cordais, problema sanduíche para grafos-(2,1) com G2 sem triângulos e problema sanduíche para grafos-(2,1) com grau máximo de G2 igual a k, fixo. O problema para grafos fortemente cordais-(2,1), mostramos ser NP-completo e os outros três, polinomiais.
O foco deste trabalho são problemas sanduíche aos quais atribuímos propriedades específicas aos seus grafos de entrada, que chamamos de condições de contorno. A estes "problemas sanduíche generalizados" demos o nome de problemas sanduíche com condições de contorno. Nosso objetivo consiste em tentar transformar problemas conhecidos e que têm solução difícil em problemas mais maleáveis e possivelmente solucionáveis em tempo polinomial. Trabalhamos com quatro problemas que não haviam sido estudados: problema sanduíche para grafos fortemente cordais-(2,1) e três problemas sanduíche para grafos-(2,1) com condições de contorno, a saber: problema sanduíche para grafos-(2,1) com G1 e G2 cordais, problema sanduíche para grafos-(2,1) com G2 sem triângulos e problema sanduíche para grafos-(2,1) com grau máximo de G2 igual a k, fixo. O problema para grafos fortemente cordais-(2,1), mostramos ser NP-completo e os outros três, polinomiais.
Abstract
This thesis introduces a new work proposal related to sandwich problems. This kind of problem, in its original form, was introduced in 1995 by Golumbic, Kaplan and Shamir and it can be de ned as follows: Given two graphs G1 = (V,E1) and G2 = (V,E2) such that E1 is subset of E2, is there a graph G = (V,E) such that E1 is subset of E that is subset of E2 and G satisfi es a given property P? The focus of this work are sandwich problems to which we assigned special conditions to its input graphs, that we called boundary conditions. We called these "generalized sandwich problems" by sandwich problems with boundary conditions. We have introduced them in an attempt to transform some difficult known problems into problems more tractable and possibly solvable in polynomial time. We have worked with four problems that haven't been studied yet: (2,1)-strongly chordal graphs sandwich problem and three (2,1)-graph sandwich problems with boundary conditions, that are: (2,1)-graph sandwich problem with G1 and G2 chordal, (2,1)-graph sandwich problem with G2 triangle-free and (2,1)-graph sandwich problems with maximum degree of G2 as a fixed number k. We have proved that the problem for strongly-chordal graphs is NP-complete and the other three problems are polynomial.
Arquivo