O problema probe particionado split bem-coberto é polinomial

  • S. R. Alves
  • F. Couto
  • L. Faria
  • S. Klein
  • U. dos S. Souza

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.

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 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3170.