Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: Problemas de decomposição de fluxos em redes

Data: 11/12/2024
Horário: 10h
Local: Sala de Seminários – Bloco 952

Resumo:

Fluxos em redes são uma ferramenta fundamental na Teoria dos Grafos, com muitas aplicações práticas. Uma rede N é formada por um (multi)digrafo D juntamente com uma função de capacidade u : A(D) → R+, e é denotada por N = (D, u). Um fluxo em N é uma função x : A(D) → R+ de modo que x(a) ≤ u(a) para todo a ∈ A(D). Dizemos que um fluxo é λ-uniforme se seu valor em cada arco com fluxo positivo é exatamente λ, para algum λ ∈ R+. Segundo Granata et al. (2013), redes arco-coloridas são usadas para modelar diferenças qualitativas entre as diversas regiões por onde o fluxo será enviado. Elas têm aplicações em diversas áreas tais como redes de comunicação, transportes multi-modais, biologia molecular, empacotamento etc. Neste trabalho, consideramos dois tipos de fluxos – (s, t)-fluxo e fluxo s-ramificado. Um (s, t)-fluxo representa a quantidade de fluxo que pode ser enviada de s a t em uma rede N = (D, u). De acordo com Baier, Köhler e Skutella (2005), um (s, t)-fluxo é k-divisível se ele pode ser decomposto em até k caminhos. Nós consideramos o problema de decompor um (s, t)-fluxo em uma rede arco-colorida com custo mínimo, isto é, com a menor soma do custo de seus caminhos, onde o custo de cada caminho é dado pelo seu número de cores. Mostramos que esse problema é N P-Difícil para (s, t)-fluxos em geral. Quando restringimos o prolema a (s, t)-fluxos λ-uniformes, mostramos que ele pode ser resolvido em tempo polinomial em redes com no máximo duas cores, e é N P-Difícil para redes em geral com três cores e para redes acíclicas com pelo menos cinco cores. Um fluxo s-ramificado deve alcançar todos os outros vértices de uma rede N = (D, u) a partir de s, perdendo uma unidade de fluxo em cada vértice diferente de s. Segundo Bang-Jensen e Bessy (2014), quando u ≡ n − 1, a rede admite k fluxos s-ramificados arco-disjuntos se e somente se D contém k s-ramificações arco-disjuntas. Assim, um resultado clássico de Edmonds (1973), que diz que um digrafo contém k s-ramificações se e somente se o grau de entrada de todo conjunto X ⊆ V (D)\{s} for pelo menos k, também caracteriza a existência de k fluxos s-ramificados arco-disjuntos nessas redes. Neste trabalho, investigamos como uma propriedade que é uma extensão natural da caracterização de Edmonds está relacionada à existência de k fluxos s-ramificados arco-disjuntos em redes. Embora essa propriedade seja sempre necessária para a existência de tais fluxos, nós mostramos que ela nem sempre é suficiente e que é difícil decidir se os fluxos desejados existem, mesmo se tivermos o conhecimento prévio de que ela é satisfeita.

Banca examinadora:

• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC) – Orientadora
• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC) – Coorientadora
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
• Prof. Dr. Carlos Vinícius Gomes Costa Lima (UFCA)