SOBRE A COMPLEXIDADE DO PROBLEMA CLIQUE COVER EM REPRESENTAÇÕES {⌞}-EPG

Vol 55, 2023 - 160999
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

CLIQUE COVER é um problema clássico da teoria dos grafos, onde dado um grafo G e um inteiro k, devemos verificar se V(G) pode ser coberto por no máximo k cliques. Os grafos {⌞}-EPG são uma subclasse da classe dos grafos de interseção de caminhos em grades EPG (edge intersection graphs of paths on a grid), onde em uma representação {⌞}-EPG todo caminho efetuar no máximo uma dobra e possui somente um dos seguintes formatos: {⌞, −, |}. Neste artigo, provamos que CLIQUE COVER em representações {⌞}-EPG e NP-completo e apresentamos um algoritmo FPT capaz de resolvê-lo utilizando o número de cliques da solução como parâmetro. Além disso, mostramos também que o problema CLIQUE COVER em representações ∂EPG2 (subclasse de {⌞}- EPG) e solucionável em tempo polinomial.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal Fluminense
  • 2 Universidade Federal do Tocantins
Eixo Temático
  • 19. TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Clique Cover; {⌞}-EPG; Complexidade Computacional