Problema do subgrafo planar otimo (1994)
- Authors:
- Autor USP: CARMO, RENATO JOSÉ DA SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: TEORIA DOS GRAFOS
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 05.05.1994
-
ABNT
CARMO, Renato Jose da Silva. Problema do subgrafo planar otimo. 1994. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1994. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005412/. Acesso em: 25 fev. 2026. -
APA
Carmo, R. J. da S. (1994). Problema do subgrafo planar otimo (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005412/ -
NLM
Carmo RJ da S. Problema do subgrafo planar otimo [Internet]. 1994 ;[citado 2026 fev. 25 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005412/ -
Vancouver
Carmo RJ da S. Problema do subgrafo planar otimo [Internet]. 1994 ;[citado 2026 fev. 25 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005412/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
