Skip to Main content Skip to Navigation
New interface
Journal articles

Packing of Mixed Hyperarborescences with Flexible Roots via Matroid Intersection

Florian Hoersch 1 Zoltán Szigeti 1 
1 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : Given a mixed hypergraph $\mathcal{F}=(V,\mathcal{A}\cup \mathcal{E})$, a non-negative integer $k$ and functions $f,g:V\rightarrow \mathbb{Z}_{\geq 0}$, a packing of $k$ spanning mixed hyperarborescences of $\mathcal{F}$ is called $(k,f,g)$-flexible if every $v \in V$ is the root of at least $f(v)$ and at most $g(v)$ of the mixed hyperarborescences. We give a characterization of the mixed hypergraphs admitting such packings. This generalizes results of Frank and, more recently, Gao and Yang. Our approach is based on matroid intersection, generalizing a construction of Edmonds. We also obtain an algorithm for finding a minimum weight solution to the problem mentioned above.
Document type :
Journal articles
Complete list of metadata
Contributor : Zoltán Szigeti Connect in order to contact the contributor
Submitted on : Wednesday, August 25, 2021 - 3:41:57 PM
Last modification on : Thursday, July 7, 2022 - 11:59:29 AM

Links full text




Florian Hoersch, Zoltán Szigeti. Packing of Mixed Hyperarborescences with Flexible Roots via Matroid Intersection. The Electronic Journal of Combinatorics, 2021, 28 (3), ⟨10.37236/10105⟩. ⟨hal-03326074⟩



Record views