Título: Problemas Inaproximáveis em Grafos.

Data: 06/11/2015 Horário: 16h Local: Bloco 952 - Sala 02 (Campus do Pici)

Resumo:

Os problemas NP-completos são usualmente considerados intratáveis na literatura. Uma possível forma de contornar esta dificuldade é a construção de algoritmos aproximativos para estes problemas, no entanto algumas vezes a aproximação obtida pode não ser satisfatória. Se há um limite $r$ para o qual nenhum algoritmo de tempo polinomial pode obter um $r$-aproximação de um problema $P$, então $P$ é dito $r$-inaproximável. Outra possível maneira de contornar a dificuldade de um problema NP-completo é a contrução de algoritmos para entradas com propriedades específicas e que possam tornar o problema tratável. Nesta monografia estudamos os problemas de lid-coloração e o jogo de policia e ladrão em grafos. Para o primeiro mostramos um resultado de inaproximabilidade, bem como um algoritmo linear para grafos $P_4$-esparsos. Para o segundo, mostramos valores exatos para o copnumber e o $k$-capture time de grafos $P_4$-laden, além disso mostramos que a conjectura de Meyniel é válida para grafos $P_4$-laden conexos. Também estudamos um novo problema de perseguição criado por N. Nisse chamado de Jogo do Espião e mostramos que o mesmo é NP-completo e, além disso, inaproximável por um determinado fator.

Banca:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC)
• Prof. Dr. Júlio César Silva Araújo (UFC)