Problemas de teoria dos grafos, alguns considerados difíceis (NP-difíceis), serão estudados e classes de grafos em que tais problemas admitem soluções eficientes serão pesquisados. Estudaremos suas complexidades computacionais, seus algoritmos e buscaremos por classes de grafos nas quais o comportamento do ponto de vista de complexidade possa ser determinado. Propomos o estudo de: soluções exatas para problemas NP-difíceis; dois problemas de coloração de arestas, restringindo a classes específicas e buscando determinar sua complexidade; problemas relacionados com o grafo biclique; um problema relacionado com conectividade, e técnicas espectrais para algoritmos em grafos. Estes problemas se enquadram na área de otimização combinatória.
Processo: 428941/2016-8
Instituição de Vínculo/Execução: Universidade Federal do Paraná / UFPR
Chamada: Universal 01/2016 - Faixa B - até R$ 60.000,00
Recursos:
| Capital | Custeio | Bolsa | Valor Total |
| R$ 13.500,00 | R$ 40.284,00 | R$ 0,00 | R$ 53.784,00 |
Implantação (assinatura do termo de aceitação): 13/06/2017
Prazo do projeto: 36 meses + 24 meses de prorrogação
Encerramento: Prorrogado até 31/05/2022 (2 vezes)
O projeto foi prorrogado, devido à pandemia de CoViD-19, por mais 12 meses, por duas vezes. Para cada um destes estes pedidos foram elaborados relatórios parciais e planos de trabalho.
Projeto concluído e Relatório Final entregue e aprovado.
Alunos de doutorado:
Alunos de mestrado:
Alunos de graduação: