Skip to Main content Skip to Navigation
Journal articles

Polymatroid-based capacitated packing of branchings

Tatsuya Matsuoka Zoltán Szigeti 1
1 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the spanning arborescence packing problem to a matroid-based arborescence packing problem and gave a necessary and sufficient condition for the existence of a packing and a polynomial-time algorithm. In this paper, a generalization of this latter problem – the polymatroid-based arborescence packing problem – is considered. Two problem settings are formulated: an unsplittable version and a splittable version. The unsplittable version is shown to be strongly NP-complete. Whereas, the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, can be solved in strongly polynomial time. For convenience, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for the splittable version.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-02350547
Contributor : Zoltán Szigeti <>
Submitted on : Wednesday, November 6, 2019 - 9:09:00 AM
Last modification on : Tuesday, May 11, 2021 - 11:37:25 AM

Identifiers

  • HAL Id : hal-02350547, version 1

Collections

Citation

Tatsuya Matsuoka, Zoltán Szigeti. Polymatroid-based capacitated packing of branchings. Discrete Applied Mathematics, Elsevier, 2019, 270, pp.13. ⟨hal-02350547⟩

Share

Metrics

Record views

152