Exportar registro bibliográfico

Aproximações para restrições do problema de Steiner em grafos (2004)

  • Authors:
  • USP affiliated authors: MARTINEZ, FABIO HENRIQUE VIDUANI - IME
  • Unidades: IME
  • Sigla do Departamento: MAC
  • Subjects: ALGORITMOS E ESTRUTURAS DE DADOS
  • Language: Português
  • Abstract: 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ãoem 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.
  • Imprenta:
  • Data da defesa: 19.08.2004

  • How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      MARTINEZ, Fábio Henrique Viduani; SOARES, José Augusto Ramos. Aproximações para restrições do problema de Steiner em grafos. 2004.Universidade de São Paulo, São Paulo, 2004.
    • APA

      Martinez, F. H. V., & Soares, J. A. R. (2004). Aproximações para restrições do problema de Steiner em grafos. Universidade de São Paulo, São Paulo.
    • NLM

      Martinez FHV, Soares JAR. Aproximações para restrições do problema de Steiner em grafos. 2004 ;
    • Vancouver

      Martinez FHV, Soares JAR. Aproximações para restrições do problema de Steiner em grafos. 2004 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020