COMPLEXIDADE PARAMETRIZADA PARA PROBLEMAS EM GRAFOS E/OU

  • Uéverton dos Santos Souza Universidade Federal Fluminense
  • Fábio Protti Universidade Federal Fluminense
  • Maise Dantas da Silva Universidade Federal Fluminense

Resumo

Grafos E/Ou e Grafos X-de-Y são estruturas capazes de modelar muitos problemas (teóricos e práticos) nas mais diversas áreas de aplicação. Uma vez modelado um problema com uma dessas estruturas, geralmente sua solução poderá ser obtida através de um subgrafo (subgrafo-solução) deste grafo. Neste trabalho, são estudados os problemas Min–E/Ou e Min–X-de-Y, que consistem, respectivamente, em encontrar um subgrafo-solução de custo mínimo em grafos E/Ou e grafos X-de-Y. Como ambos são problemas NP-difíceis, este trabalho foca em abordagens parametrizadas para Min–E/Ou e Min–X-de-Y, obtendo alguns resultados quanto à tratabilidade parametrizada das versões Min–E/Ou(k,r), Min–X-de-Y(k) e Exato–X-de-Y(k) destes problemas.

Palavras-chave: Complexidade Parametrizada. Grafos E/Ou. Grafos X-de-Y

Biografia do Autor

Uéverton dos Santos Souza, Universidade Federal Fluminense

Programa de Pós Graduação em Computação (UFF)

Instituto Três Rios (UFRRJ)

Fábio Protti, Universidade Federal Fluminense
Instituto de Computação
Maise Dantas da Silva, Universidade Federal Fluminense
Instituto de Ciência e Tecnologia
Publicado
22-06-2012
Como Citar
Souza, U., Protti, F., & da Silva, M. (2012). COMPLEXIDADE PARAMETRIZADA PARA PROBLEMAS EM GRAFOS E/OU. Pesquisa Operacional Para O Desenvolvimento, 4(2), 160-174. Recuperado de https://podesenvolvimento.org.br/podesenvolvimento/article/view/102
Seção
Artigos