COMPLEXIDADE PARAMETRIZADA PARA PROBLEMAS EM GRAFOS E/OU

摘要

Grafos E/Ou e Grafos X-de-Y s?￡o estruturas capazes de modelar muitos problemas (te?3ricos 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 Mina€“E/Ou e Mina€“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 Mina€“E/Ou e Mina€“X-de-Y, obtendo alguns resultados quanto ?? tratabilidade parametrizada das vers?μes Mina€“E/Ou(k,r), Mina€“X-de-Y(k) e Exatoa€“X-de-Y(k) destes problemas. Palavras-chave: Complexidade Parametrizada. Grafos E/Ou. Grafos X-de-Y