O problema probe particionado split bem-coberto é polinomial

  • S. R. Alves FAETEC/RJ
  • F. Couto UFRRJ
  • L. Faria UERJ
  • S. Klein UFRJ
  • U. dos S. Souza UFF

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

Alves, S. R., Dabrowski, K. K., Faria, L., Klein, S., Sau, I., and Souza, U. S. (2016). On the (parameterized) complexity of recognizing well-covered (r, l)-graphs. In COCOA 2016, Hong Kong, China, 2016, pages 423 – 437. LNCS.

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.
Publicado
26/07/2018
ALVES, S. R.; COUTO, F.; FARIA, L.; KLEIN, S.; SOUZA, U. dos S.. O problema probe particionado split bem-coberto é polinomial. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . p. 133-136. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3170.