Exportar registro bibliográfico

K-árvores de custo mínimo (2010)

  • Authors:
  • Autor USP: OSHIRO, MARCIO TAKASHI IURA - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: OTIMIZAÇÃO COMBINATÓRIA
  • Agências de fomento:
  • Language: Português
  • Abstract: Esta dissertação trata do problema da k-árvore de custo mínimo (k-MST): dados um grafo conexo G, um custo não-negativo Ce para cada aresta e, e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação.
  • Imprenta:
  • Data da defesa: 11.06.2010
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      OSHIRO, Marcio Takashi Iura; PINA JÚNIOR, José Coelho de. K-árvores de custo mínimo. 2010.Universidade de São Paulo, São Paulo, 2010. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652 >.
    • APA

      Oshiro, M. T. I., & Pina Júnior, J. C. de. (2010). K-árvores de custo mínimo. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652
    • NLM

      Oshiro MTI, Pina Júnior JC de. K-árvores de custo mínimo [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652
    • Vancouver

      Oshiro MTI, Pina Júnior JC de. K-árvores de custo mínimo [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652

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

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