Transversais de caminhos mais longos em grafos

• Processo: 23/14346-8
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de fevereiro de 2024
• Data de Término da vigência: 31 de janeiro de 2026
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Yoshiko Wakabayashi
• Beneficiário: Heloisa de Lazari Bento
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Grafos Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: caminhos mais longos | grafos | transversais | Teoria dos grafos

Resumo

Este projeto se insere na área de teoria dos grafos. O seu foco é a investigação de problemas sobre caminhos mais longos em grafos, com ênfase no estudo de transversais mínimas de tais caminhos. Num grafo conexo um conjunto de vértices que intersecta cada caminho mais longo desse grafo é chamado uma transversal (de caminhos mais longos). Sabe-se que nem todos os grafos possuem transversais de cardinalidade 1. Temos interesse em estudar certas classes de grafos e determinar limitantes superiores para transversais mínimas de grafos nessas classes. Outras variantes deste problema (quando se restringe o número de caminhos mais longos) também serão investigados.