Decomposição de Fluxos em Digrafos Arco-Coloridos
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.
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
Como Citar
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.
