On the helly property of some intersection graphs

• Ano de defesa: 2020
• Autor(a) principal: Santos, Tanilson Dias dos
• Orientador(a): Szwarcfiter, Jayme Luiz
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Rio de Janeiro
• Programa de Pós-Graduação: Programa de Pós-Graduação em Filosofia em Engenharia de Sistemas e Computação
• País: Brasil
• Palavras-chave em Português: EPG; EPT; Grafos de Interseção; NP-completude; Propriedade Helly; VPG; VPT; Helly property; Intersection graphs; NP-completeness
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://hdl.handle.net/11612/3663

EPG é um grafo de aresta-interseção de caminhos sobre uma grade. Nesta tese de doutorado exploraremos principalmente os grafos EPG, em particular os grafos B1-EPG. Entretanto, outras classes de grafos de interseção serão estu dadas, como as classes de grafos VPG, EPT e VPT, além dos parâmetros número de Helly e número de Helly forte nos grafos EPG e VPG. Apresentaremos uma prova de NP-completude para o problema de reconhecimento de grafos B1-EPG Helly. Investigamos os parâmetros número de Helly e o número de Helly forte nessas duas classes de grafos, EPG e VPG, a fim de determinar limites inferiores e superi ores para esses parâmetros. Resolvemos completamente o problema de determinar o número de Helly e o número de Helly forte para os grafos Bk-EPG e Bk-VPG, para cada valor k. Em seguida, apresentamos o resultado de que todo grafo B1-EPG Chordal está simultaneamente nas classes de grafos VPT e EPT. Em particular, descrevemos estruturas que ocorrem em grafos B1-EPG que não suportam uma representação B1-EPG-Helly e assim definimos alguns conjuntos de subgrafos que delimitam sub famílias Helly. Além disso, também são apresentadas características de algumas famílias de grafos não triviais que estão propriamente contidas em B1-EPG-Helly