Plenária Odelar Leite Linhares: Yoshiko Wakabayashi, USP, Brasil

 

(A palestra será em Português)

 

Título: Conjuntos dominantes localizadores de densidade mínima na grade hexagonal infinita com altura limitada

 

Resumo: Na teoria dos grafos e em otimização combinatória, o conceito de conjunto dominante e suas variantes têm sido largamente investigados, sendo vasta a literatura a respeito. Um conjunto dominante num grafo é um conjunto C de vértices tal que todo vértice do grafo não pertencente a C tem pelo menos um vizinho em C. Dizemos que C é um Conjunto Dominante Localizador (CDL), se para cada par de vértices distintos u e v não pertencentes a C, a vizinhança de u em C e a vizinhança de v em C são distintas.

O problema de encontrar um CDL mínimo é NP-difícil. Ele foi introduzido por Slater em 1975, motivado por aplicações em que o grafo modela uma rede (um ambiente) e sensores são usados para vigiar a presença de intrusos.  Relativamente a este problema, nosso interesse é considerar grades infinitas, e encontrar CDL's de densidade mínima. Focaremos aqui a grade hexagonal infinita com altura limitada k (conhecida por ter a estrutura de uma colméia).

Veremos como construir um grafo auxiliar para obter soluções ótimas periódicas para grades infinitas com altura até 6.  Adicionalmente, veremos o uso de uma formulação linear inteira para obter soluções viáveis de boa qualidade para grades com alturas 7 e 8.  Mostraremos como combinar esses resultados, e obter soluções explícitas para qualquer k > 9.  Veremos que tais soluções ou são ótimas ou estão a menos de 1% da solução ótima.