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

Construcao de algoritmos eficientes para problemas np-dificeis em grafos

Carvalheiro, Fabio Henrique

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

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

  • Título:
    Construcao de algoritmos eficientes para problemas np-dificeis em grafos
  • Autor: Carvalheiro, Fabio Henrique
  • Orientador: Feofiloff, Paulo
  • Assuntos: Algoritmos E Estruturas De Dados; Teoria Dos Grafos
  • Notas: Dissertação (Mestrado)
  • Descrição: 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
  • DOI: 10.11606/D.45.1994.tde-20220712-114614
  • 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-06-01
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  4 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.