Partitioning split graphs into two trees

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 19. TAG – Teoria e Algoritmos em Grafos
  • Palavras chaves: Partição em Grafos; grafos de Yutsis; grafos Split;
  • 1 Universidade Federal Fluminense

Partitioning split graphs into two trees

Uéverton Souza

Universidade Federal Fluminense

Resumo

Seja G = (V,E) um grafo simples e não direcionado. Neste trabalho, consideramos o problema de particionar V (G) = A∪B, A∩B = ∅, tal que cada A e B induzem uma árvore (i.e, um subgrafo acíclico e conexo). Os grafos que admitem essa partição foram denominados grafos de Yutsis e seus estudos estão relacionados aos estudos de grafos planares Hamiltonianos. O reconhecimento de grafos de Yutsis é NP-completo para grafos gerais e, até o momento, não há estudos considerando a caracterização de grafos de Yutsis para classes de grafos específicas. Este trabalho se restringe a reconhecer grafos split (grafos cujo conjunto de vértices pode ser particionado em um conjunto independente e num clique) que são de Yutsis. Mais especificamente, fornecemos uma caracterização por subgrafos proibidos que conduz a um algoritmo polinomial de reconhecimento dos grafos split que são Yutsis.

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!