• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Gao, Hui (Gao, Hui.) [1] | Yang, Daqing (Yang, Daqing.) [2]

Indexed by:

EI SCIE

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:

Arborescence Matroid Mixed graph Packing Supermodularity

Community:

  • [ 1 ] [Gao, Hui]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Fujian, Peoples R China
  • [ 2 ] [Yang, Daqing]Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China

Reprint 's Address:

  • [Yang, Daqing]Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

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:

WoS CC 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

Online/Total:192/10796353
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1