skip to main content
Idioma:
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

Passeios e conexidade em grafos mistos: algorithmos e complexidade computacional

Lee, Orlando

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 1994-12-20

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Passeios e conexidade em grafos mistos: algorithmos e complexidade computacional
  • Autor: Lee, Orlando
  • Orientador: Wakabayashi, Yoshiko
  • Assuntos: Teoria Dos Grafos
  • Notas: Dissertação (Mestrado)
  • Descrição: 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)
  • DOI: 10.11606/D.45.1994.tde-20210729-005856
  • 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: 1994-12-20
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  2 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.