Indexed by:
Abstract:
This paper studies the following packing problem: Given a mixed graph F with vertex set V, a matroid M on a set S = {s(1), ..., s(k)} along with a map pi: S -> V, find k mutually edge and arc-disjoint mixed arborescences T-1, ..., T-k in F with roots pi(s(1)), ..., pi(s(k)) such that, for any upsilon is an element of V, the set {s(i) : upsilon is an element of V(T-i)} is independent and its rank reaches the theoretical maximum. This problem was mentioned by Fortier, Kiraly, Leonard, Szigeti and Talon in [Old and new results on packing arborescences in directed hypergraphs, Discrete Appl. Math. 242 (2018), 26-33]; Matsuoka and Tanigawa gave a solution to this in [On reachability mixed arborescence packing, Discrete Optimization 32 (2019) 1-10]. In this paper, we give a new characterization for above packing problem. This new characterization is simplified to the form of finding a supermodular function that should be covered by an orientation of each strong component of a matroid-based rooted mixed graph. Our proofs come along with a polynomial-time algorithm. The technique of using components opens some new ways to explore arborescence packings. (C) 2020 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE APPLIED MATHEMATICS
ISSN: 0166-218X
Year: 2021
Volume: 289
Page: 313-319
1 . 2 5 4
JCR@2021
1 . 0 0 0
JCR@2023
ESI Discipline: ENGINEERING;
ESI HC Threshold:105
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: