Detalhes bibliográficos
| Ano de defesa: |
1997 |
| Autor(a) principal: |
Rodrigues, Estela Maris |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013855/
|
Resumo: |
Uma generalização de emparelhamentos em grafos pode ser obtida com base na idéia de encontrarmos, em um garfo H = (V(H),A(H)), um subgrafo G tal que os componentes de G sejam isomorfos a membros de uma família fixa F de grafos conexos. Ao grafo G chamamos F-empracotamento de H, e se V (G) = V(H), então G é denominado um F-fator de H. Um de nossos objetivos é o estudo da complexidade dos problemas da forma 'dado um grafo H, decidir se H admite um F-fator'. Chamamos este problema de problema de fatoração definido por F. Os problemas de fatoração definidos por famílias unitárias foram os primeiros a serem estudados. Dentre esses, o problema do emparelhamento perfeito é o único, em essência, que não é NP-completo. Dentre os problemas definidos por famílias não unitárias, são conhecidas algumas classes de problemas polinomiais. Exemplos são os problemas de fatoração por famílias de cliques que contenham o grafo 'K IND.2', e alguns problemas definidos por familias de estrelas. Todos esses problemas são considerados neste trabalho. Também apresentamos exemplos de problemas NP-completos definidos por famílias não unitárias de grafos, por exemplo o problema do {'K IND.3', 'K IND.4',...}-fator e alguns problemas definidos por famílias de grafos bipartidos completos. Atualmente, a maior questão acerca dos problemas de fatoração é a conjectura de Loebl e Poljak, que propõe uma caracterização das famílias de grafos conexos que definem problemas de fatoração polinomiais em termos de matróides. Essa conjectura foi respondida de forma afirmativa para famílias da forma {'K IND.2', F} em que F é um grafo conexo. O caso geral permanece em aberto desde que foi proposto em 1988 |
