Yoshiko gave the Odelar Leite Linhares Plenary talk at CNMAC 2025. Yoshiko talked about locating-dominating sets on infinite grids with finite height.

More details can be found here.

Abstract of the talk (in Portuguese): 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.