Defesa de Proposta de Tese de Doutorado de Rodrigo dos Anjos Azevedo, em 24/10/23, às 14:30h, na sala 208 do Instituto de Computação.
Partição de Grafos em Árvores Induzidas
Resumo:
Este trabalho aborda o problema da Partição de Grafos em Árvores Induzidas. Dado um grafo G, definimos ca(G) como o menor número k de subgrafos induzidos G1,G2,…,Gk tais que cada Gi é uma árvore e UI=1KV(Gi) = V(G). As árvores são exatamente a classe dos grafos G para os quais ca(G) = 1, enquanto que os grafos G com ca(G) ≤ 2 são conhecidos na literatura como grafos de Yutsis. Em particular, grafos planares particionáveis em duas árvores induzidas correspondem exatamente à classe dual dos grafos planares Hamiltonianos. O reconhecimento de grafos de Yutsis é NP-completo, e portanto determinar uma cobertura mínima por árvores induzidas de um grafo G é um problema computacionalmente difícil. O principal resultado desta proposta de tese é uma caracterização da classe dos cografos de Yutsis, bem como um algoritmo eficiente para verificar se um cografo é de Yutsis, através da análise da estrutura de co-árvores.
Abstract:
This paper addresses the problem of Graph Partition into Induced Trees. Given a graph G, we define ca(G) as the minimum number k of induced subgraphs G1,G2,…,Gk such that each Gi is a tree and UI=1KV(Gi) = V (G). Trees are precisely the class of graphs G for which ca(G) = 1, while graphs G with ca(G) ≤ 2 are known in the literature as Yutsis graphs. In particular, planar graphs partitionable into two induced trees correspond exactly to the dual class of Hamiltonian planar graphs. The recognition of Yutsis graphs is NP-complete, thus determining a minimum covering by induced trees of a graph G is a computationally difficult problem. The main result of this thesis proposal is a characterization of the class of Yutsis cographs, as well as an efficient algorithm to verify if a cograph is a Yutsis graph by analyzing the structure of cotrees.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Fábio Protti, UFF
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Luis Antônio Brasil Kowada, UFF
Profa. Loana Tito Nogueira, UFF
Profa. Sulamita Klein, UFRJ