Polymatroid-based capacitated packing of branchings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

Polymatroid-based capacitated packing of branchings

Tatsuya Matsuoka
  • Fonction : Auteur
  • PersonId : 1057657
Zoltán Szigeti

Résumé

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 et versions

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

Identifiants

Citer

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 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More