Skip to Main content Skip to Navigation
Journal articles

Packing of Mixed Hyperarborescences with Flexible Roots via Matroid Intersection

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

https://hal-cnrs.archives-ouvertes.fr/hal-03326074
Contributor : Zoltán Szigeti <>
Submitted on : Wednesday, August 25, 2021 - 3:41:57 PM
Last modification on : Thursday, August 26, 2021 - 1:47:37 PM

Links full text

Identifiers

Collections

Citation

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

Share

Metrics

Record views

9