Defesa de Mestrado de Natanael Ramos

Título do Trabalho
Um Estudo Computacional do Problema do Brigadista em Grafos
Candidato(a)
Natanael Ramos
Nível
Mestrado
Data
Add to Calender 2018-04-13 00:00:00 2018-04-13 00:00:00 Defesa de Mestrado de Natanael Ramos Um Estudo Computacional do Problema do Brigadista em Grafos Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
09:30
Local
Sala 85 IC 2
Orientador(a)
Cid Carvalho de Souza
Banca Examinadora

Condição

Titulares  -  Professores Doutores

Unidade/Instituição

Orientador/Presidente

Cid Carvalho de Souza

IC/UNICAMP

Externo à Unidade

Luciana Salete Buriol

II/UFRGS

Interno à Unidade

Fábio Luiz Usberti

IC/UNICAMP

 

Condição

Suplentes  -  Professores Doutores

Unidade/Instituição

Interno à Unidade

Orlando Lee

IC/UNICAMP

Externo à Unidade

Kelly Cristina Poldi

IMECC/UNICAMP

Resumo

O Problema do Brigadista em Grafos (FFP do inglês \textit{The Firefighter Problem} é um modelo determinístico e em tempo discreto para simular a propagação e contenção de incêndios em grafos. Ele pode ser descrito da seguinte forma. Na entrada, é dado um inteiro $D$ representando a quantidade de brigadistas disponíveis, um grafo não direcionado e não ponderado $G = (V,E)$ e um subconjunto de vértices $B \subseteq V$, os focos de incêndio. Então, inicia-se nos elementos de $B$ um processo iterativo de propagação e contenção de fogo através dos vértices de $G$, em rodadas discretas , o qual termina quando não existem mais vértices que possam ser queimados, ou seja, quando o fogo está contido. O objetivo ao resolver o FFP é maximizar o número de vértices não queimados quando o fogo é contido, com a restrição de que no máximo $D$ vértices podem ser protegidos contra o fogo por rodada. Aplicações práticas do FFP, além da obtenção de estratégias para minimização de danos causados por incêndios, podem ser encontradas em áreas como controle de doenças e segurança em redes.