ESTRUTURAS DISCRETAS E COMPLEXIDADE COMPUTACIONAL DA RESOLUÇÃO DE PROBLEMAS COMBINATÓRIOS DE INTERESSE LOGÍSTICO

O projeto Estruturas discretas e complexidade computacional da resolução de problemas combinatórios de interesse logístico é uma continuação da pesquisa realizada na tese [4] que foi elaborada e defendida na Universidade Federal do Rio de Janeiro-UFRJ, em 2022. A proposta é o desenvolvimento de pesquisas acadêmicas na área de algoritmos aplicados à resolução de problemas combinatórios descritos em Grafos, aqui na UFPa. Muitos desses problemas são de interesse diretamente da logística empresarial de segurança e até mesmo para tratamento computacional biológico. O direcionamento da pesquisa começa na tentativa de escrever algoritmos, preferencialmente de tempo bom de execução, para resolver alguns problemas combinatórios em grafos, problemas esses que se encontram em aberto. Um desses problemas é o problema da busca do parâmetro do número de envoltória, restrito às convexidade P3 e geodética, em subclasses específicas dos grafos clique-expandidos. Os grafos clique-expandidos são uma classe de grafos introduzida na tese [4]. O parâmetro do número de envoltória, é muito utilizado no estudo de contaminações epidêmicas de interesse computacional e biológico, devido ao grande poder que o referido parâmetro tem de modelar ataques virtuais a redes de computadores e epidemias de doenças contagiosas em populações potencialmente suscetíveis. Um outro problema também de muito interesse que pretendemos estudar, no decorrer do tempo de execução deste projeto, é o problema do caixeiro viajante e, principalmente, suas variantes mais fáceis. Resolver uma variante do problema do caixeiro viajante é encontrar um algoritmo, de tempo de execução preferencialmente polinomial, que resolva a variante em questão, ou seja, o algoritmo precisa resolver o problema na classe restrita de grafos que vai na entrada do problema, este problema se propõe a encontrar rotas ótimas que minimizem o tempo de percurso de translado de mercadorias e/ou passageiros em rotas comerciais e/ou turísticas.