Decomposição de Fluxos em Digrafos Arco-Coloridos - Carvalho, Cláudio; Costa, Jonas; Maia, Ana Karolinna; Sales, Cláudia Linhares (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
Sejam N uma rede sobre um digrafo D e x um (s, t)-fluxo viável em N. Dizemos que x é ℓ-divisível se ele pode ser decomposto em até ℓ fluxos caminhos. Neste artigo, consideramos o problema de obter uma decomposição em caminhos em digrafos arco-coloridos, de modo que a soma do número de cores dos caminhos seja mínima. Nós mostramos que, dado fluxo x em uma rede N sobre um digrafo arco-colorido e um inteiro k, é NP-completo decidir se há uma decomposição de x em caminhos, tal que a soma do número de cores dos caminhos seja no máximo k, e mostramos alguns casos para os quais isso pode ser feito em tempo polinomial.