Decomposição de Fluxos em Digrafos Arco-Coloridos

  • Cláudio Carvalho UFC
  • Jonas Costa UFC
  • Ana Karolinna Maia UFC
  • Cláudia Linhares Sales UFC

Resumo


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.

Referências

Baier, G., Köhler, E., and Skutella, M. (2005). The k-splittable flow problem. Algorithmica, 42(3–4).

Ford Jr., L. R. and Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press, Princeton, NJ, 1 ed.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, 1 ed.

Granata, D., Cerulli, R., Scutellà, M. G., and Raiconi, A. (2013). Maximum flow problems and an NP-Complete variant on edge-labeled graphs. In Pardalos, P. M., Du, D.-Z., and Graham, R. L., editors, Handbook of Combinatorial Optimization, pages 1913–1948. Springer New York, New York, NY.

Kleinberg, J. M. (1996). Single-source unsplittable flow. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, pages 68–77, Burlington, Vermont. IEEE Computer Society.
Publicado
06/08/2023
CARVALHO, Cláudio; COSTA, Jonas; MAIA, Ana Karolinna; SALES, Cláudia Linhares. Decomposição de Fluxos em Digrafos Arco-Coloridos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 6-9. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230750.