Homeomorfismo em grafos: algoritmos e complexidade computacional (1993)
- Authors:
- Autor USP: BENATTI, HAROLDO GONÇALVES - IME
- Unidade: IME
- Sigla do Departamento: MAP
- Assunto: TEORIA DOS GRAFOS
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 29.10.1993
-
ABNT
BENATTI, Haroldo Goncalves. Homeomorfismo em grafos: algoritmos e complexidade computacional. 1993. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1993. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-004351/. Acesso em: 26 maio 2024. -
APA
Benatti, H. G. (1993). Homeomorfismo em grafos: algoritmos e complexidade computacional (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-004351/ -
NLM
Benatti HG. Homeomorfismo em grafos: algoritmos e complexidade computacional [Internet]. 1993 ;[citado 2024 maio 26 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-004351/ -
Vancouver
Benatti HG. Homeomorfismo em grafos: algoritmos e complexidade computacional [Internet]. 1993 ;[citado 2024 maio 26 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-004351/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
