Título: Um Estudo de Redes com Fluxos Ramificados Arco-disjuntos

Data: 11/03/2019

Horário: 08:30h

Local: Sala de Reuniões - Bloco 910

Resumo:

Redes e fluxos são utilizados na modelagem de problemas de diversos domínios diferentes, desde roteamento, circuitos elétricos,  redes de computadores até a generalização de problemas de caminhos em digrafos. No conceito de fluxos arco-disjuntos, introduzido por (BANG-JENSEN; BESSY, 2014), não estamos interessados apenas em encontrar um fluxo viável em uma rede, mas sim múltiplos fluxos viáveis que sejam arco-disjuntos entre si. Essa generalização permitiu a modelagem de novos problemas utilizando os conceitos familiares de fluxo, desde problemas polinomiais, como aquele de decidir se um multigrafo direcionado possui k ramificações arco-disjuntas, a problemas N P-completos, como o problema de encontrar caminhos arco-disjuntos entre vértices pré-determinados. Neste trabalho, realizamos um estudo sobre fluxos arco-disjuntos com enfoque em fluxos ramificados, que são fluxos que possuem um vértice fonte que envia fluxo para todos os demais vértices, de modo que cada um dos demais retenha uma unidade de fluxo. Tendo como parâmetro a função de capacidade da rede, estudamos também a complexidade do problema de encontrar fluxos ramificados arco disjuntos. A partir de resultados de (EDMONDS, 1973) e (BANG- JENSEN et al., 2016), propomos uma conjectura que caracteriza (ainda com base na função de capacidade) as redes que possuem múltiplos fluxos ramificados arco-disjuntos e mostramos alguns casos em que ela é válida.

Banca:

• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC - Orientadora)
• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC - Orientadora)
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
• Prof. Dr. Raphael Carlos Santos Machado (CEFET/RJ)