Carlos Eduardo Rodrigues Alves (carlos@ime.usp.br)
6a. feira - 12 de março - 15 horas
Sala 139 - B
Resumo:
Uma variante dos jogos de pesquisa em grafos envolve a busca
de um fugitivo invisível que se esconde nas suas arestas,
usando um número mínimo de guardas. Os guardas podem ser removidos
e recolocados nos vértices livremente.
Uma aresta é considerada limpa quando:
a) um guarda a atravessa de vértice a vértice ("edge search")
b) há guardas em ambos os vértices da aresta ("node search")
Porém, se um guarda é removido ou deslocado, o vértice que ele
ocupava pode ficar temporariamente desguarnecido e pode ser usado
pelo fugitivo para voltar para áreas anteriormente limpas.
Se esta "recontaminação" não ocorre, temos uma busca monotônica.
Será mostrada uma demonstração de Bienstock e Seymour (90) de que sempre há uma busca monotônica usando um número mínimo de guardas, ou seja, permitir recontaminações não reduz o número de guardas a serem usados. Usando este resultado pode-se chegar a resultados anteriores de LaPaugh (envolvendo "edge search" somente) e Kirousis & Papadimitriou (somente "node search"). Este tipo de problema está intimamente ligado a problemas de "path decomposition" e (no caso de fugitivos visíveis) "tree decomposition".