• 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
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.1994.tde-20210729-005043
Documento
Autor
Nome completo
Ronaldo Fumio Hashimoto
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 1994
Orientador
Título em português
Circuitos e caminhos pares/impares em grafos e digrafos - algoritmo e complexidade computacional
Palavras-chave em português
Algoritmos E Estruturas De Dados
Computabilidade E Complexidade
Resumo em português
Neste trabalho estudamos varios problemas sobre circuitos e caminhos em grafos e em digrafos. Consideramos aqui tres classes de problemas: de existencia, de busca e de busca de um minimo. Para cada uma dessas classes investigamos os casos em que o objeto em questao e um circuito par/impar ou um caminho par/impar. Discutimos questoes referentes a complexidade computacional desses problemas e apresentamos algoritmos polinomiais para resolver varios deles. A maioria dos resultados que apresentamos foram coletados da literatura, incluindo uma resenha atualizada sobre o problema da existencia de circuitos pares em digrafos (um problema cuja complexidade computacional continua desconhecida ha vinte anos). Nossa principal contribuicao a este estudo e o desenvolvimento de um algoritmo linear para encontrar circuitos impares em digrafos. Descrevemos tambem algoritmos alternativos (nao necessariamente de melhor complexidade) para alguns dos problemas
Título em inglês
not available
Resumo em inglês
not available
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-07-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.