Defesa de Qualificação de Mestrado: Jhonata Adam Silva Matias
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)