Seminário


Algoritmos para encontrar Buracos em Grafos (Ciclos sem cordas)


Palestrante(s): Luidi Gelabert Simonetti

Local: Canal no Youtube "PPCIC CEFET-RJ"

Data: 19/05/2022 às 19:30

Tópico(s): Grafos Heurísticas Programação Matemática

Link para a apresentação


Resumo: Apresentaremos formulações e algoritmos exatos e heurísticos para o problema de ciclo sem cordas (buraco). Esse problema consiste em encontrar o maior ciclo em um dado grafo que não contenha nenhuma aresta ligando vértices não consecutivos no ciclo. Esse problema tem relação forte com diversos outros problemas como Caixeiro Viajante (TSP), Roteamento de veículos, Maior Ciclo, entre outros. Generalizações dos métodos propostos serão comentados para esses problemas.

 

Biografia: Possui graduação em Engenharia Mecânica pela UFRJ e doutorado em Engenharia de Sistemas e Computação pela UFRJ. Atualmente é Professor Associado da PESC/COPPE/UFRJ, coordenador do curso de Engenharia de Computação e Informação POLI/UFRJ, Jovem Cientista do Nosso Estado FAPERJ e Bolsista de Produtividade em Pesquisa do CNPq. Tem experiência na área de Ciência da Computação, com ênfase em Design e Análise de Algoritmos, Otimização Combinatória, Programação Matemática, Teoria de grafos e Inteligência Computacional.