Um estudo de redes com fluxos ramificados arco-disjuntos

Abstract

Network flows constitute a very useful tool for modeling problems of different areas such as: routing, electrical circuits, computer networks and even path problems on digraphs. The arc-disjoint flows problem was introduced by (BANG-JENSEN; BESSY, 2014) and it is a generalization of the classical flow problem in which we are interested in deciding whether a network admits multiple arc-disjoint feasible flows. On this generalized version, is possible to model new problems using flow tools, from polynomial ones, such as the problem of finding multiple arc-disjoint out-branchings, to N P-complete ones, such as the problem of deciding whether exists arc-disjoint paths between prescribed pairs of vertices. In this work, we study the arc-disjoint flow problem with focus on branching flows, which are flows where a vertex sends a unit of flow to all the other vertices. Considering the network capacity function as parameter we studied the complexity of finding two arc-disjoint branching flows. Based on results of (EDMONDS, 1973) and (BANG-JENSEN et al., 2016) we proposed a conjecture to characterize (also based on the capacity function) the networks which admit multiple arc-disjoint branching flows and we also showed some cases where it holds.