• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.1994.tde-20210729-005412
Document
Auteur
Nom complet
Renato Jose da Silva Carmo
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 1994
Directeur
Titre en portugais
Problema do subgrafo planar otimo
Mots-clés en portugais
Teoria Dos Grafos
Resumé en portugais
Este trabalho trata do problema de determinar um subgrafo planar de peso maximo de um grafo dado. Uma demonstracao simplificada da np-completude do problema e apresentada. Descrevemos uma implementacao alternativa do conhecido algoritmo de teste de planaridade de hopcroft/tarjan, adequada para uso com subrotina reiteradamente invocada sobre um grafo nao necessariamente biconexo. Baseados nessa abordagem, propomos uma implementacao nao-ingenua do metodo guloso para a determinacao de solucoes aproximadas do problema, cujo tempo de execucao e significativamente menor que o das implementacoes mencionadas na literatura. Resultados experimentais dessa implementacao sao exibidos e analisados. O limite de desempenho absoluto para o metodo guloso aplicado ao problema do subgrafo planar otimo e determinado. Outras heuristicas encontradas na literatura sao apresentadas de maneira unificada e analisadas comparativamente. Uma parte do trabalho e dedicada a uma detalhada descricao do algoritmo de teste de planaridade, com a finalidade de servir de texto de referencia para algoritmos baseados na estrategia de hopcroft/tarjan. Nessa discussao, introduzimos a ideia de hierarquias como uma interessante ferramenta conceitual para a descricao formal das propriedades de uma busca em profundidade num grafo
Titre en anglais
not available
Resumé en anglais
not available
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.