skip to main content
Visitante
Meu Espaço
Minha Conta
Sair
Identificação
This feature requires javascript
Tags
Revistas Eletrônicas (eJournals)
Livros Eletrônicos (eBooks)
Bases de Dados
Bibliotecas USP
Ajuda
Ajuda
Idioma:
Inglês
Espanhol
Português
This feature required javascript
This feature requires javascript
Primo Search
Busca Geral
Busca Geral
Acervo Físico
Acervo Físico
Produção Intelectual da USP
Produção USP
Search For:
Clear Search Box
Search in:
Produção Intelectual da USP
Or hit Enter to replace search target
Or select another collection:
Search in:
Produção Intelectual da USP
Busca Avançada
Busca por Índices
This feature requires javascript
Tipo de recurso
criteria input
qualquer lugar do registro
no título
como autor
no assunto
Data de publicação
lsr01
lsr02
lsr03
lsr04
Orientador
Show Results with:
no título
Show Results with:
qualquer lugar do registro
no título
como autor
no assunto
Data de publicação
lsr01
lsr02
lsr03
lsr04
Orientador
Mostra resultados com:
criteria input
que contêm minhas palavras de busca
com a frase exata
começa com
Mostra resultados com:
Índice
criteria input
E
OU
NÃO
This feature requires javascript
Homeomorfismo em grafos: algoritmos e complexidade computacional
Benatti, Haroldo Goncalves
Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 1993-10-29
Acesso online. A biblioteca também possui exemplares impressos.
Exibir Online
Localização & Reservas
Detalhes
Resenhas & Tags
Solicitações
Mais Opções
Prateleira Virtual
This feature requires javascript
Enviar para
Adicionar ao Meu Espaço
Remover do Meu Espaço
E-mail (máximo 30 registros por vez)
Imprimir
Link permanente
Referência
EasyBib
EndNote
RefWorks
del.icio.us
Exportar RIS
Exportar BibTeX
This feature requires javascript
Título:
Homeomorfismo em grafos: algoritmos e complexidade computacional
Autor:
Benatti, Haroldo Goncalves
Orientador:
Wakabayashi, Yoshiko
Assuntos:
Teoria Dos Grafos
Notas:
Dissertação (Mestrado)
Descrição:
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
DOI:
10.11606/D.45.1993.tde-20210729-004351
Editor:
Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
Data de criação/publicação:
1993-10-29
Formato:
Adobe PDF
Idioma:
Português
Links
Este item no Dedalus
Teses e Dissertações USP
This feature requires javascript
This feature requires javascript
Voltar para lista de resultados
Anterior
Resultado
7
Avançar
This feature requires javascript
This feature requires javascript
Buscando em bases de dados remotas. Favor aguardar.
Buscando por
em
scope:(USP_PRODUCAO)
Mostrar o que foi encontrado até o momento
This feature requires javascript
This feature requires javascript
Anterior
Página Inicial
RSS
Feed
Políticas
Fale Conosco
Logos de Redes Sociais: 
Logos de Redes Sociais: