Reconhecimento linear de uma partição Stable Tree mínima em grafos P4-tidy

  • Fábio Júnior UFF
  • Uéverton Souza UFF
  • Raquel Bravo UFF
  • Rodolfo Alves de Oliveira UFF

Resumo


Neste trabalho consideramos o problema de encontrar um conjunto de vértices S mínimo de um grafo P4-tidy G, tal que o subgrafo induzido por G \ S seja uma árvore e S seja estável. Este problema foi provado ser NPcompleto para grafos gerais em Brandstädt et al. 1998. Apresentamos um algoritmo para reconhecimento de um conjunto S mínimo nos grafos P4-tidy baseado numa caracterização por subgrafos proibidos minimais. Através da análise do algoritmo, provamos que este problema de otimização pode ser resolvido em tempo linear.

Palavras-chave: Grafos, algoritmo de reconhecimento, Otimização

Referências

Baumann, S. (1996). A linear algorithm for the homogeneous decomposition of graphs.

Brandstädt, A., Szymczak, T., et al. (1998). The complexity of some problems related to graph 3-colorability. Discrete Applied Mathematics, 89(1-3):59–73.

Földes, S. and Hammer, P. L. (1977). Split graphs having dilworth number two. Canadian Journal of Mathematics, 29(3):666–672.

Giakoumakis, V., Roussel, F., and Thuillier, H. (1997). On p4-tidy graphs. Discrete Mathematics and Theoretical Computer Science, 1.

Huang, Y. and Chu, Y. (2007). A note on the computational complexity of graph vertex partition. Discrete applied mathematics, 155(3):405–409.

Jamison, B. and Olariu, S. (1995). P-components and the homogeneous decomposition of graphs. SIAM Journal on Discrete Mathematics, 8(3):448–463.

Roussel, F., Rusu, I., and Thuillier, H. (1999). On graphs with limited number of p4-partners. International Journal of Foundations of Computer Science, 10(01):103–121.

Saaty, T. (1977). The four-color problem : assaults and conquest. McGraw-Hill International Book Co, New York.

Silva, F., Bravo, R., Oliveira, R., and Souza, U. (2018). Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-p4-tidy. In 3º Encontro de Teoria da Computação (ETC), volume 3. SBC.

Silva, F., Bravo, R., Oliveira, R., and Souza, U. (2019). Algoritmo de reconhecimento da partição s mínima em grafos p4-tidy STABLE TREE. https://bit.ly/2GNidhv. [Online; acessado 14-Fevereiro-2019].
Publicado
20/04/2019
JÚNIOR, Fábio; SOUZA, Uéverton; BRAVO, Raquel; DE OLIVEIRA, Rodolfo Alves. Reconhecimento linear de uma partição Stable Tree mínima em grafos P4-tidy. In: ESCOLA REGIONAL DE INFORMÁTICA DO RIO DE JANEIRO (ERI-RJ), 3. , 2019, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 25-28.