Passeios e conexidade em grafos mistos: algorithmos e complexidade computacional (1994)
- Authors:
- Autor USP: LEE, ORLANDO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: TEORIA DOS GRAFOS
- Language: Português
- Abstract: Nesta dissertacao estudamos varios problemas relacionados com grafos mistos. Tais grafos generalizam a nocao de grafos nao orientados e orientados, no sentido de e que podem conter tanto arco como arestas. Assim, procuramos estudar problemas sobre esses grafos que fossem extencoes naturais de problemas conhecidos sobre grafos nao-orientados e orientados. Tres problemas bastante conhecidos foram tratados no nosso trabalho: o problema de encontrar uma trilha fechada euleriana, o problema do carteiro chines e o problema do caminho minimo. Discutimos a complexidade computacional desses problemas e descrevemos algoritmos polinomiais para alguns (casos particulares) deles. Problemas de orientacao formam outra classe natural de problemas dentro do contexto de grafos mistos. Em particular, estudamos o problema de encontrar orientacoes fortemente conexas e o problema mais geral de encontrar orientacoes k-aresta-conexas de grafos mistos. Por fim, estudamos tambem o problema de aumentar a aresta-conexidade local de grafos mistos. Mais precisamente, estudamos o problema de encontrar um conjunto minimo de arestas (arcos) a serem acrescentados (os) a um grafo misto de modo que no grafo resultante a aresta conexidade entre cada par (u,v) de vertices distintos seja pelo menos um valor pre-estabelecido r (u,v)
- Imprenta:
- Data da defesa: 20.12.1994
-
ABNT
LEE, Orlando. Passeios e conexidade em grafos mistos: algorithmos e complexidade computacional. 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-005856/. Acesso em: 13 fev. 2026. -
APA
Lee, O. (1994). Passeios e conexidade em grafos mistos: algorithmos 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-005856/ -
NLM
Lee O. Passeios e conexidade em grafos mistos: algorithmos e complexidade computacional [Internet]. 1994 ;[citado 2026 fev. 13 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005856/ -
Vancouver
Lee O. Passeios e conexidade em grafos mistos: algorithmos e complexidade computacional [Internet]. 1994 ;[citado 2026 fev. 13 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005856/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
