Polymatroid-based capacitated packing of branchings
| Autor: | Tatsuya Matsuoka, Zoltán Szigeti |
|---|---|
| Přispěvatelé: | Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]) |
| Rok vydání: | 2019 |
| Předmět: |
021103 operations research
Arborescence Generalization Applied Mathematics Graph algorithm 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Directed graph Arborescence packing 01 natural sciences Matroid Combinatorics Packing problems 010201 computation theory & mathematics Strongly polynomial [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Discrete Mathematics and Combinatorics Polymatroid Graph algorithms Arc capacity Mathematics |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, Elsevier, 2019, 270, pp.13. ⟨10.1016/j.dam.2019.06.014⟩ |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.06.014 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect