Convexidades em Grafos: Intermediações, Parâmetros e Conversões
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
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.
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.