Detalhes bibliográficos
| Ano de defesa: |
1993 |
| Autor(a) principal: |
Benatti, Haroldo Goncalves |
| 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-004351/
|
Resumo: |
Neste trabalho estudamos varios problemas que envolvem homeomorfismo de grafos procurando responder questoes referentes a sua complexidade computacional e a existencia de algoritmos polinomiais para resolve-los. Estudamos relacoes entre aresta-homeomorfismo e vertice-homeomorfismo. Algumas destas relacoes sao utilizadas para provar a np-completude de varios problemas de homeoformismo sem padraofixo. No caso orientado, para os problemas com padrao fixo sao conhecidos algoritmos polinomiais, para apenas alguns padroes. Ja no caso nao orientado, existe um algoritmo polinoamial que resolve o problema de qualquer padrao, mas este algoritmo nao e suscetivel a uma implementacao eficiente. Isto motivou o estudo destes problemas com entradas restritas a classes particulares de grafos. Apresentamos algoritmos polinomiais, em alguns casos bem eficientes, para a classe dos grafosplanares. Por ultimo estudamos a complexidade de alguns problemas de modularidade de caminhos e circuitos em grafos orientados. Estes resultados foram obtidos usando problemas de homeomorfismo com padrao fixo. Analisamos a complexidade desses mesmos problemas quando restritos a classe dos grafos bipartidos e constatamos que esta restricao, em geral, nao altera a complexidade destes problemas |
