COMPLEXIDADE PARAMETRIZADA PARA PROBLEMAS EM GRAFOS E/OU

Autores

  • 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

Downloads

Publicado

2012-06-22

Como Citar

Souza, U. dos S., Protti, F., & da Silva, M. D. (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

Edição

v. 4 n. 2 (2012)

Seção

Artigos

Licença

A submissão de um artigo implica que ela foi aprovada por todos os coautores, se for o caso, bem como pelas autoridades responsáveis da instituição onde o trabalho foi realizado e que o(s) autor(es) estará(ão) implicitamente cedendo seus direitos à SOBRAPO e afirmando que eventuais direitos autorais de terceiros não estão sendo violados. O(s) autor(es), entretanto, permanece(m) responsável(is) pelo conteúdo do artigo publicado na revista. Apesar de se acreditar que a informação divulgada seja verdadeira e acurada na data de sua publicação, os editores e a SOBRAPO não aceitam qualquer responsabilidade legal por erros e omissões que possam ter ocorrido ou que venham a ser identificados.