Convexidades em Grafos: Intermediações, Parâmetros e Conversões - dos Santos, Vinicius; Szwarcfiter, Jayme; Rautenbach, Dieter (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC), 2014)
Inspirados no conceito de convexidade da geometria euclideana, diversos trabalhos envolvendo convexidades abstratas vêm sendo feitos recentemente. Nesta tese consideramos o caso particular de convexidades em grafos, o qual pode ser utilizado para modelar diversas aplicações, como influência em redes sociais, sistemas distribuídos e automata celular, dentre outras. São abordados problemas envolvendo intermediações, o número de envoltória, o número de Radon, o número de Carathéodory e conversões com limite de tempo em grafos. Os resultados apresentados compreendem caracterizações, algoritmos eficientes para a determinação de parâmetros, provas de NPcompletude e limites superiores e inferiores.