Sobre a Dificuldade de Reconhecimento de Grafos B1-EPG-Helly

  • Claudson Bornstein
  • Tanilson Santos
  • Uéverton Souza
  • Jayme Szwarcfiter

Resumo


Golumbic, Lipshteyn e Stern definiram em 2009 os grafos EPG, uma classe de grafos de intersecção baseada na intersecção de arestas de caminhos em uma grade. Um grafo EPG G é um grafo que admite um esquema de representação onde seus vértices são representados por caminhos de uma grade Q, de forma que dois vértices em G são adjacentes se e somente se os caminhos correspondentes em Q compartilham arestas. Se tais caminhos em Q tem no máximo k mudanças de direção (dobras), então a representação é dita BkEPG. Uma coleção C de conjuntos satisfaz a propriedade Helly quando toda subcoleção de C que é mutuamente intersectante possui pelo menos um elemento comum. Neste trabalho mostramos que o reconhecimento de grafos que admitem representação B1-EPG satisfazendo a propriedade Helly é NP-difícil.

Publicado
26/07/2018
BORNSTEIN, Claudson; SANTOS, Tanilson; SOUZA, Uéverton; SZWARCFITER, Jayme. Sobre a Dificuldade de Reconhecimento de Grafos B1-EPG-Helly. 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.3148.