Fluxos Ramificados Arco-disjuntos em Redes de Capacidade Restrita⇤

  • A. Karolinna Maia
  • Jonas Costa
  • Raul Lopes

Resumo


Determinar se uma rede possui um fluxo viável é um problema amplamente estudado e que pode ser resolvido em tempo polinomial. Investigamos um tipo específico de fluxo, o fluxo ramificado, que pode ser aplicado na busca por ramificações em digrafos. Consideramos o problema de encontrar múltiplos fluxos ramificados arco-disjuntos em uma rede e estudamos a complexidade deste problema 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).

Publicado
26/07/2018
MAIA, A. Karolinna; COSTA, Jonas; LOPES, Raul. Fluxos Ramificados Arco-disjuntos em Redes de Capacidade Restrita⇤. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3162.