• 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-20220712-114614
Documento
Autor
Nome completo
Fabio Henrique Carvalheiro
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 1994
Orientador
Título em português
Construcao de algoritmos eficientes para problemas np-dificeis em grafos
Palavras-chave em português
Algoritmos E Estruturas De Dados
Teoria Dos Grafos
Resumo em português
Arnborg (1985) e robertson/seymour (1986) introduziram, de modo independente, um conceito que se mostra uma boa medida da complexidade de um grafo g: dimensao de g (arnborg) ou tree-width de g (robertson, seymour). O primeiro autor apresenta um paradigma para desenvolver algoritmos polinomias, quando restritos a grafos com dimensao limitada para diversos problemas np-dificeis. Os outros utilizam o conceito de tree-width para resolver a conjectura well-quasi-ordering de k. Wagner e apresentar um algoritmo polinomial para o problema dos k caminhos disjuntos. O conceito de tree-width foi aproveitado por bodlander para paralelizar o paradigma de arnborg e mostrar que varios problemas np-dificeis, quando restritos a grafos com tree-width limitada, estao na classe nc. Neste trabalho apresentamos o paradigma de arnborg, generalizado e melhor formalizado, juntamente com sua aplicacao a quatro problemas np-completos, rigorosamente analisados: conjunto estavel maximo, clique maximo, coloracao minima e circuito hamiltoniano. Em seguida fazemos uma demonstracao construtiva (original) da equivalencia entre dimensao e tree-width de um grafo. Por ultimo, estudamos o problema de se determinar a dimensao (tree-width) de um dado grafo e apresentamos algumas classes de grafos com dimensao (tree-width) limitada
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
2022-07-13
 
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-2022. Todos os direitos reservados.