COMPLEXIDADE PARAMETRIZADA PARA PROBLEMAS EM GRAFOS E/OU - Souza, Uéverton dos Santos; Protti, Fábio; da Silva, Maise Dantas (Pesquisa Operacional para o Desenvolvimento, 2012)
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