Reconhecimento linear de uma partição Stable Tree mínima em grafos P4-tidy
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].
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
Como Citar
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.
