Problemas de M-partição em cografos - Bravo, Raquel Souza Francisco; Cruz, Maria Luíza López (Anais do Encontro de Teoria da Computação (ETC), 2020)
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,*}.