Defesa de Doutorado de Andrei de Almeida Sampaio Braga

Título do Trabalho
An Eternal Domination Problem: Graph Classes, Solving Methods, and Practical Standpoint
Candidato(a)
Andrei de Almeida Sampaio Braga
Nível
Doutorado
Data
Add to Calender 2019-12-05 00:00:00 2019-12-05 00:00:00 Defesa de Doutorado de Andrei de Almeida Sampaio Braga An Eternal Domination Problem: Graph Classes, Solving Methods, and Practical Standpoint Auditório 2 do IC 3 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
09:30
Local
Auditório 2 do IC 3
Orientador(a)
Cid Carvalho de Souza
Banca Examinadora

* Titulares

Unidade/Instituição

Cid Carvalho de Souza

IC/UNICAMP

Daniel Morgato Martin

CMCC/UFABC

Mário César San Felice

DC/UFSCar

Cláudio Leonardo Lucchesi

IC/UNICAMP

Eduardo Candido Xavier

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Guilherme Pimentel Telles

IC/UNICAMP

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Alexandre da Silva Freire

EACH/USP

Resumo

O problema do conjunto dominante m-eterno é um problema de otimização em grafos que tem sido muito estudado nos últimos anos e para o qual se têm listado aplicações em vários domínios. O objetivo é determinar o número mínimo de guardas que consigam defender eternamente ataques nos vértices de um grafo; denominamos este número o índice de dominação m-eterna do grafo. Nesta tese, estudamos o problema do conjunto dominante m-eterno: lidamos com aspectos de natureza teórica e prática e abordamos o problema restrito a classes específicas de grafos e no caso geral. Examinamos o problema do conjunto dominante m-eterno com respeito a duas classes de grafos: os grafos de Cayley e os conhecidos grafos de intervalo próprios. Primeiramente, mostramos ser inválido um resultado sobre os grafos de Cayley presente na literatura, provamos que o resultado é válido para uma subclasse destes grafos e apresentamos outros achados. Em segundo lugar, fazemos descobertas em relação aos grafos de intervalo próprios, incluindo que, para estes grafos, o índice de dominação m-eterna é igual à cardinalidade máxima de um conjunto independente e, por consequência, o índice de dominação m-eterna pode ser computado em tempo linear. Tratamos de uma questão que é fundamental para aplicações práticas do problema do conjunto dominante m-eterno, mas que tem recebido relativamente pouca atenção. Para tanto, introduzimos dois métodos heurísticos, nos quais formulamos e resolvemos modelos de programação inteira e por restrições para computar limitantes ao índice de dominação m-eterna. Realizamos um vasto experimento para analisar o desempenho destes métodos. Neste processo, geramos um benchmark contendo 750 instâncias e efetuamos uma avaliação prática de limitantes ao índice de dominação m-eterna disponíveis na literatura. Por fim, propomos e implementamos um algoritmo exato para o problema do conjunto dominante m-eterno e contribuímos para o entendimento da sua complexidade: provamos que a versão de decisão do problema é NP-difícil. Pelo que temos conhecimento, o algoritmo proposto foi o primeiro método exato a ser desenvolvido e implementado para o problema do conjunto dominante m-eterno.