Lista 6
Considere o algoritmo sequencial FPT para o problema de
k-cobertura de vértices de um grafo,
reduzindo primeiro o problema para um núcleo
(heurística de Buss) e depois gerando
uma árvore de busca ternária pelo método de depth-first
até obter a solução ou até concluir que não há solução.
Adote um exemplo de um grafo qualquer e
mostre (1) o que resulta após a transformação
ao núcleo e (2) a árvore de busca ternária
gerada pelo algoritmo de depth-first.
(Dica: veja o exemplo e as figuras da aula 25.)
Last modified: Mon Jun 21 13:40:11 EST 2004