Polymatroid-based capacitated packing of branchings - Archive ouverte HAL Access content directly
Journal Articles Discrete Applied Mathematics Year : 2019

Polymatroid-based capacitated packing of branchings

, (1)
1
Tatsuya Matsuoka
  • Function : Author
  • PersonId : 1057657
Zoltán Szigeti

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.

Dates and versions

hal-02350547 , version 1 (06-11-2019)

Identifiers

Cite

Tatsuya Matsuoka, Zoltán Szigeti. Polymatroid-based capacitated packing of branchings. Discrete Applied Mathematics, 2019, 270, pp.13. ⟨10.1016/j.dam.2019.06.014⟩. ⟨hal-02350547⟩
38 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More