• 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
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2004.tde-20210729-140037
Documento
Autor
Nombre completo
Fábio Henrique Viduani Martinez
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2004
Director
Título en portugués
Aproximações para restrições do problema de Steiner em grafos
Palabras clave en portugués
Algoritmos E Estruturas De Dados
Resumen en portugués
No problema de Steiner em grafos é dado um grafo completo com custos nas arestas e um subconjunto de vértices chamados terminais e queremos encontrar uma árvore de menor custo que conecte todos os terminais. Este trabalho aborda restrições desse problema. Os problemas abordados têm aplicações em construção de árvores filogenéticas em biologia, roteamento local ou global no projeto de placas VLSI, transporte e telecomunicações, bem como são úteis para se estabelecer a complexidade computacional para os problemas sem restrições. O primeiro problema abordado é o da árvore de Steiner de terminais folhas, onde exigimos que os terminais sejam folhas na árvore resultante. O segundo problema é o da árvore de Steiner de terminais folhas com custos 1 ou 2 nas arestas. Apresentamos algoritmos de aproximação que melhoram as razões de aproximação previamente conhecidas para esses problemas. Propomos também uma nova variante do problema, na qual uma permutação dos vértices terminais também é dada como entrada. Queremos encontrar agora uma árvore de Steiner de menor custo que respeite a permutação dada. Dizemos que a árvore respeita a permutação se sempre que terminais 'r IND.1', 'r IND. 2', 'r IND. 3'e 'r IND. 4' aparecem nesta ordem na permutação, os caminhos na árvore entre 'r IND. 1' a 'r IND. 3' e entre 'r IND. 2'a 'r IND. 4' têm pelo menos um vértice em comum. Mostramos que árvores k-restritas são aproximações para esse problema na mesma razão que o são em geral para o problema de Steiner em grafos. E mostramos um algoritmo que encontra em tempo polinomial uma árvore k-restrita ótima para esta versão do problema.
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
2021-07-29
 
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-2021. Todos los derechos reservados.