Packing of mixed hyperarborescences with flexible roots via matroid intersection (Q2048562)

From MaRDI portal
Revision as of 08:23, 26 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Packing of mixed hyperarborescences with flexible roots via matroid intersection
scientific article

    Statements

    Packing of mixed hyperarborescences with flexible roots via matroid intersection (English)
    0 references
    0 references
    0 references
    9 August 2021
    0 references
    Summary: 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 \textit{A. Frank} [in: Algebraic methods in graph theory. Vol. I, II. Conference held in Szeged, August 24--31, 1978. Amsterdam-Oxford-New York: North-Holland Publishing Company. 159--169 (1981; Zbl 0507.05054)] and, more recently, \textit{H. Gao} and \textit{D. Yang} [``Packing of spanning mixed arborescences'', Preprint, \url{arXiv:2005.03218}]. 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.
    0 references
    mixed graphs
    0 references
    edge-disjoint spanning trees
    0 references
    arborescences
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references