Este projeto tem como objetivo principal investigar problemas combinatórios computacionalmente difíceis em grafos. O projeto se articula em diversas frentes, sendo que a maior delas se refere a atacar tais problemas em famílias de grafos que possuam propriedades prescritas. Tais propriedades são determinadas tanto por características estruturais dos grafos (como caracterização por subgrafos induzidos proibidos e por propriedades de particionamento ou ordenação do conjunto de vértices ou de arestas), quanto pela distribuição esperada dos graus de vértices (abordagem vinda da teoria de grafos aleatórios e da teoria de redes complexas). Adicionalmente, o projeto investiga o comportamento de algoritmos exatos para problemas NP-difíceis em grafos em geral (não apenas classes restritas).
Processo: 420079/2021-1
Instituição de Vínculo/Execução: Universidade Federal do Paraná / UFPR
Chamada: Universal 18/2021 - Faixa A
Recursos:
| Capital | Custeio | Bolsa | Valor Total |
| R$ 13.750,00 | R$ 129.675,00 | R$ 0,00 | R$ 143.425,00 |
Implantação (assinatura do termo de aceitação): 03/02/2022
Prazo do projeto: 36 meses + 12 meses de prorrogação
Encerramento: Prorrogado até 28/02/2026
Alunos de doutorado:
Alunos de mestrado:
Alunos de graduação: