Linear recognition of a minimum Stable Tree partition in P4-tidy graphs
Abstract
In this work we consider the problem of finding a set of vertices S minimum of a graph P4-tidy G, such that the subgraph induced by G n S is a tree and S is a stable set. It was showed that this problem is NP-complete for general graphs in Brandstädt et al. 1998. We present an algorithm for finding a minimum set S in P4-tidy graphs based on a characterization by minimal forbidden subgraphs. Through the analysis of the algorithm, we prove that this optimization problem can be solved in linear time.
Keywords:
Grafos, algoritmo de reconhecimento, Otimização
References
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].
Published
2019-04-20
How to Cite
JÚNIOR, Fábio; SOUZA, Uéverton; BRAVO, Raquel; DE OLIVEIRA, Rodolfo Alves.
Linear recognition of a minimum Stable Tree partition in P4-tidy graphs. In: REGIONAL SCHOOL ON INFORMATICS OF RIO DE JANEIRO (ERI-RJ), 3. , 2019, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 25-28.
