O problema probe particionado split bem-coberto é polinomial
Resumo
Um grafo G = (V,E) é bem-coberto se cada conjunto independente maximal de G é máximo. Um grafo G = (V,E) é split se existe uma partição V = (S,K), onde S é um conjunto independente e K é uma clique. Um grafo split bem-coberto é, ao mesmo tempo, split e bem-coberto. Dada uma classe C de grafos, um grafo G = (V,E) é C−probe se existe uma partição para V = (N,P) em probes P e não-probes N, onde N é um conjunto independente e novas arestas podem ser adicionadas entre não-probes de maneira que o grafo resultante permaneça na classe de grafos C. Dizemos que (N,P) é uma C probe partição para G. O problema C−PROBE PARTICIONADO consiste de um grafo de entrada G e uma partição probe V = (N,P) e a questão: (N,P) é uma C−partição probe? Neste artigo, consideramos C como a classe dos grafos split bem-cobertos, e provamos que o problema C−PROBE PARTICIONADO pertence à classe de problemas polinomiais P.
Referências
Chvátal, V. and Slater, P. J. (1993). A note on well-covered graphs. In John Gimbel, J. W. K. and Quintas, L. V., editors, Quo Vadis, Graph Theory?, volume 55 of Annals of Discrete Mathematics, pages 179 – 181. Elsevier.
Feder, T., Hell, P., Klein, S., and Motwani, R. (1999). Complexity of graph partition problems. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC ’99, pages 464 – 472. ACM, New York, NY, USA.
Golumbic, M., Kaplan, H., and Shamir, R. (1995). Graph sandwich problems. volume 19, pages 449 – 473.
Golumbic, M. C. (1980). Algorithmic graph theory and perfect graphs. In Academic Press, volume 1, pages 149 – 156. Elsevier Science.
