• 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
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.1994.tde-20220712-114614
Documento
Autor
Nombre completo
Fabio Henrique Carvalheiro
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 1994
Director
Título en portugués
Construcao de algoritmos eficientes para problemas np-dificeis em grafos
Palabras clave en portugués
Algoritmos E Estruturas De Dados
Teoria Dos Grafos
Resumen en 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 en inglés
not available
Resumen en inglés
not available
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2022-07-13
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.