Autores

5360
Vinícius Fernandes dos Santos
2425,6,2426
5361
2425,6,2426
5362
Dieter Rautenbach
(Co-orientador)
2425,6,2426

Informações:

Publicações do PESC

Título
Convexidades em Grafos: Intermediações, Parâmetros e Conversões
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
30/1/2013
Resumo

Inspirados no conceito de convexidade, da geometria euclideana, diversos trabalhos vêm sendo feitos nas últimas décadas envolvendo convexidades abstratas. Nesta tese é considerado o caso particular de convexidades em grafos, o qual pode ser utilizado para modelar diversas aplicações, como influências 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 NP-completude e limites superiores e inferiores. 

Abstract

Motivated by the concept of convexity, from Euclidean geometry, much work has been done in recent decades on abstract convexities. In this thesis, the particular case of graph convexity is considered, which can be used to model many applications, such as influence on social networks, distributed systems and cellular automata, among others.
We address problems involving betweenesses, the hull number, the Radon number, the Carathéodory number and conversions with deadlines in graphs. The results shown in this thesis include characterizations, efficient algorithms for determining parameters, NP-completeness proofs, and upper and lower bounds.

Topo