Partitioning split graphs into two trees

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 19. TAG – Teoria e Algoritmos em Grafos
  • Keywords: 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

Abstract

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.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!