Defesa de Qualificação de Doutorado: Cláudio Soares de Carvalho Neto
Data da publicação: 26 de setembro de 2024 Categoria: Notícias, Qualificação de Doutorado
Título: Decomposição de fluxos em redes arco-coloridas
Data: 03/10/2024
Horário: 14h00
Local: Sala de Seminários – Bloco 952
Resumo:
Fluxos em redes são uma ferramenta fundamental da Teoria dos Grafos, com diversas aplicações práticas. Dada uma rede N sobre um digrafo D, com dois vértices s e t, um (s, t)-fluxo representa, por exemplo, a quantidade de um dado produto que pode ser enviada de uma origem s a um destino t na rede. Nesse caso, o fluxo pode ser visto como um conjunto de caminhos de s a t. De acordo com Baier, Köhler e Skutella (2005), um fluxo é l-divisível se puder ser decomposto em até l caminhos. Determinar o menor número l de modo que um fluxo x seja l-divisível é um problema N P-Completo. Segundo Granata et al. (2013), redes arco-coloridas são usadas para modelar situações em que é crucial representar diferenças qualitativas entre as regiões pelas quais o fluxo será enviado. As cores podem representar, por exemplo, fatores de risco em redes de telecomunicação, ou tipos de transporte em sistemas de transporte multimodais. Encontrar um caminho com o menor número de cores corresponde a encontrar uma rota que minimize o número de situações distintas que devem ser consideradas. Trata-se também de um problema NP-Completo, segundo Yuan, Varma e Jue (2005). Neste trabalho, propomos o problema de decompor um fluxo em uma rede arco-colorida que minimize a soma dos custos dos caminhos, onde o custo de cada caminho é dado pelo número de cores distintas deste. Mostramos que o problema é NP-Completo para redes arco-coloridas em geral. Para redes monocromáticas, se houver no máximo dois valores distintos de fluxo nos arcos, o problema pode ser resolvido em tempo polinomial; caso contrário, ele é NP-Completo. Para redes com até duas cores, se o fluxo for λ-uniforme ou se cada cor estiver associada a um valor de fluxo e o menor destes divide o maior, mostramos que o problema pode ser resolvido em tempo polinomial. Mostramos também que, mesmo para fluxos λ-uniformes, o problema permanece N P-Completo em redes em geral com 3 cores e para redes acíclicas com pelo menos 5 cores.
Banca examinadora:
- Profa. Dra. Cláudia Linhares Sales (MDCC/UFC – Orientadora)
- Profa. Dra. Ana Karolinna Maia de Oliveira (MDCC/UFC – Coorientadora)
- Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
