2020/12/27 by Florian Hörsch, Hörsch, Florian, Zoltán Szigeti +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2012.13899
arxiv created 2020/12/27 · arxiv updated 2021/03/02
Given a mixed hypergraph F=(V,A∪ E), functions f,g:V→ ℤ+ and an integer k, a packing of k spanning mixed hyperarborescences is called (k,f,g)-flexible if every v ∈ 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 above mentioned problem.