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

author:

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

Indexed by:

EI

Abstract:

This paper studies the following packing problem: Given a mixed graph F with vertex set V, a matroid M on a set S={s1,…,sk} along with a map π:S→V, find k mutually edge and arc-disjoint mixed arborescences T1,…,Tk in F with roots π(s1),…,π(sk), such that, for any v∈V, the set {si:v∈V(Ti)} is independent and its rank reaches the theoretical maximum. This problem was mentioned by Fortier, Király, Léonard, 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. © 2020 Elsevier B.V.

Keyword:

Graph structures Graph theory Optimization Polynomial approximation

Community:

  • [ 1 ] [Gao, Hui]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian; 350108, China
  • [ 2 ] [Yang, Daqing]Department of Mathematics, Zhejiang Normal University, Jinhua, Zhejiang; 321004, China

Reprint 's Address:

Email:

Show more details

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 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: 1

Affiliated Colleges:

Online/Total:395/10798529
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