Problemas de M-partição em cografos
Resumo
O estudo de grafos é um tópico importante em Ciência da Computação, no campo teórico e prático. Este trabalho consiste na resolução de um problema na área de teoria dos grafos: o problema da M-partição visa apresentar uma caracterização dos grafos cujo conjunto de vértices pode ser particionado em k conjuntos independentes e l cliques, encontrando as obstruções minimais para essa partição. Devido à dificuldade do problema da M-partição, que é NP-completo, este trabalho considera o problema restrito à classe dos cografos com matriz simétrica M de ordem 4 (m = 4). Esta matriz representa as restrições externas e internas acerca da partição desejada e suas entradas podem ser elementos {0,1,*}.
Palavras-chave:
Cografos, Partição em Grafos, M-partição
Referências
Brandstädt, A. (1996). Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics, 152(1-3):47–54.
Brandstädt, A. (1998). Corrigendum. Discrete Mathematics, 186:295.
Bravo, R. S. F. (2006). Particionamento de cografos em conjuntos independentes e cliques. Dissertação de mestrado, COPPE/UFRJ, Rio de Janeiro, RJ, Brasil.
Bravo, R. S. F., Klein, S., and Nogueira, L. (2005). Characterizing (k, l)-partitionable cographs. Eletronic Notes on Discrete Mathematics, 22:277–280.
Bravo, R. S. F., Klein, S., Nogueira, L., and Protti, F. (2011). Characterization and recognition of P4-sparse graphs partitionable into independent sets and cliques. Discrete Applied Mathematics, 159:165–173.
Feder, T., Hell, P., Klein, S., and Motwani, R. (1999). Complexity of graph partition problems. In F. W. Thatcher, R. E. M., editor, Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (STOC’99), pages 464-472. Plenum Press.
Golumbic, M. C. (1980). Algorithmic graph theory and perfect graphs. Academic Press, New York.
Jamison, B. and Olariu, S. (1995). p-components and the homogeneous decomposition of graphs. SIAM Journal on Discrete Mathematics, 8:448–463.
Leite, J. S. S. (2013). Caracterização dos cografos-(4, 0) por subgrafos proibidos com restrições externas. Dissertação de mestrado, UFF, Niterói, RJ, Brasil.
Viana, C. C. (2013). M3×3-obstrução minimal de cografos. Dissertação de mestrado, UFF, Niterói, RJ, Brasil.
Brandstädt, A. (1998). Corrigendum. Discrete Mathematics, 186:295.
Bravo, R. S. F. (2006). Particionamento de cografos em conjuntos independentes e cliques. Dissertação de mestrado, COPPE/UFRJ, Rio de Janeiro, RJ, Brasil.
Bravo, R. S. F., Klein, S., and Nogueira, L. (2005). Characterizing (k, l)-partitionable cographs. Eletronic Notes on Discrete Mathematics, 22:277–280.
Bravo, R. S. F., Klein, S., Nogueira, L., and Protti, F. (2011). Characterization and recognition of P4-sparse graphs partitionable into independent sets and cliques. Discrete Applied Mathematics, 159:165–173.
Feder, T., Hell, P., Klein, S., and Motwani, R. (1999). Complexity of graph partition problems. In F. W. Thatcher, R. E. M., editor, Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (STOC’99), pages 464-472. Plenum Press.
Golumbic, M. C. (1980). Algorithmic graph theory and perfect graphs. Academic Press, New York.
Jamison, B. and Olariu, S. (1995). p-components and the homogeneous decomposition of graphs. SIAM Journal on Discrete Mathematics, 8:448–463.
Leite, J. S. S. (2013). Caracterização dos cografos-(4, 0) por subgrafos proibidos com restrições externas. Dissertação de mestrado, UFF, Niterói, RJ, Brasil.
Viana, C. C. (2013). M3×3-obstrução minimal de cografos. Dissertação de mestrado, UFF, Niterói, RJ, Brasil.
Publicado
30/06/2020
Como Citar
BRAVO, Raquel Souza Francisco; CRUZ, Maria Luíza López.
Problemas de M-partição em cografos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 77-80.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11094.
