Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-P4-tidy

  • Fábio Silva
  • Raquel Bravo
  • Rodolfo Oliveira
  • Uéverton Souza
DOI: https://doi.org/10.5753/etc.2018.3142

Resumo


Consideramos neste trabalho o problema de particionar o conjunto de vértices de um grafo em um conjunto independente (sem arestas entre os vértices) e em umaárvore (grafo livre de ciclos e conexo) denominada (S, T)partição. Apresentaremos uma caracterização por subgrafos proibidos minimais da (S, T)-partição dos grafos restritosá classe dos grafos P4-tidy. Como resultado adicional, disponibilizamos um algoritmo de reconhecimento desta partição em tempo linear para os grafos P4-tidy, utilizando a prova de caracterização dos subgrafos proibidos.

Publicado
26/07/2018
Como Citar

Selecione um Formato
SILVA, Fábio; BRAVO, Raquel; OLIVEIRA, Rodolfo; SOUZA, Uéverton. Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-P4-tidy. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3142.