Defesa de Qualificação de Mestrado: Jonas Costa Ferreira da Silva
Título: Fluxos Ramificados Arco-disjuntos em Redes de Capacidade Restrita
Data: 19/04/2018
Horário: 08:00h
Local: Hall do Centro de Ciências - Bloco 902
Resumo:
Determinar se uma rede possui um fluxo viável é um problema amplamente estudado. Estudamos a complexidade do problema de encontrar múltiplos fluxos ramificados arco-disjuntos em uma rede com diferentes capacidades nos arcos. Um resultado anterior prova que, sob uma suposição teórica conhecida (ETH), em redes com n vértices tais que todos os arcos possuem capacidade n − f(n), para uma função limitada f, o problema é difı́cil. Estendemos este resultado mostrando que, sob a mesma hipótese, o problema também é difı́cil quando as capacidades são iguais a f (n).
Banca:
- Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC - Orientadora)
- Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC)
- Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
- Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)