Particionamento de cografos em árvores induzidas

Vol 55, 2023 - 160515
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
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 G_1,...,G_k tais que cada G_i é uma árvore e P={V(G_1),...,V(G_k)} é uma partição de 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 à 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. Neste trabalho propomos 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 sua co-árvore.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal Fluminense
Eixo Temático
  • 19. TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Cografos; grafos de Yutsis; Partição de Grafos