Título: Problema de Coloração de Fluxo

Data: 19/04/2018

Horário: 08:00h

Local: Hall do Centro de Ciências - Bloco 902

Resumo:

Uma oferta de fluxo de vértices de origem é enviada a um vértice de destino através das arestas e vértices do grafo. Um multigrafo então é gerado com os vértices e com um subconjunto das arestas do grafo original. A multiplicidade das arestas no multigrafo e limitada inferiormente pela quantidade de fluxo a ela atribuído (aresta sem fluxo não aparecem no multigrafo). O objetivo do problema então consiste em encontrar o fluxo que gera o multigrafo de menor índice cromático. Este cenário descreve o problema de coloração de fluxo que tem aplicações práticas em redes de dispositivos wireless e é polinomial para grafos bipartidos e 3-conexos. O trabalho tem como proposta elaborar formulações de programação inteira que podem ser utilizadas para resolver instâncias do problema, realizar testes computacionais sobre as formulações propostas e avaliar os casos de complexidade em aberto.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC)
• Prof. Dr. Rafael Castro de Andrade  (MDCC/UFC)