Resultados no tempo máximo e no número de envoltória nas convexidades p3 e geodésica

Abstract

Graph convexity is a concept inspired by the convexity notions in the euclidian geometry and has been receiving a lot of attention in the last few decades. Several real world applications like spread of an infection or information in a social network can be modeled using some graph convexity based on paths in the graph. In this thesis, we consider two computational problems relating to graph convexity: Hull Number and Maximum Infection Time. Fixed a convexity C, the Hull Number problem consists in, given a graph G and an integer k, determine whether the hull number of G in the convexity C is at most k. The Maximum Infection Time problem consists in, given a graph G and an integer k, determine whether the hull number of G in the convexity C is at least k. We present some polynomial algorithms for the Maximum Infection Time problem in the P3 convexity for some graph classes and when we fix the input k. We also present fixed parameter tractable algorithms when we combine the parameters maximum degree of the graph and the input k and when we combine the parameters treewidth of the graph and the input k. Additionally, we present NP-completeness results for the Maximum Infection Time problem in the P3 convexity for some graph classes and when we restrict the input k. We also prove that the problem is W[1]-hard when parameterized by the treewidth of the graph. Finally, we show that the Hull Number problem in the P3 convexity is W[1]-hard when parameterized by k even in K3-free graphs with maximum degree six. We also show that the Hull Number problem in the geodesic convexity is W[1]-hard when parameterized by k even in graphs with diameter two and when we combine the parameters treewidth of the graph and k. Furthermore, we present a XP algorithm parameterized by the treewidth of the graph that computes the hull number of a graph in the geodesic convexity.