Data: 02/12/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Connections between the flow coloring problem and the minimum maximum flow degree problem
Palestrante: Manoel Campêlo (UFC)

Resumo: Consider an arc-capacitated network G through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multigraph with the same vertices as G and an edge for each arc of G, where the edge multiplicity is the flow in the respective arc. The flow coloring problem (FCP) consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index, to be called flow chromatic index. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of G, i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining a feasible flow such that its maximum flow degree is minimum. The two problems are closely related. We recapitulate some results on FCP, including polynomial algorithms and approximation algorithms for some cases. For MMFDP, we present a polynomial time algorithm as well an ILP formulation that can be solved in polynomial time. We explore the relations between the two problems. We present lower and upper bounds for FCP based on the minimum maximum flow degree. We also comment on an approximation algorithm for FCP based on the algorithm for MMFDP.