ON MAXIMAL INDEPENDENT ARBORESCENCE PACKING

被引：10

作者：

Kiraly, Csaba ^{[1
]}

机构：

[1] Eotvos Lorand Univ, Dept Operat Res, Pazmany Peter Setany 1-C, H-1117 Budapest, Hungary

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2016年 / 30卷 / 04期

基金：

匈牙利科学研究基金会;

关键词：

arborescence; packing; matroid;

D O I：

10.1137/130938396

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

By generalizing the results of [N. Kamiyama, N. Katoh, and A. Takizawa, Combinatorica, 29 (2009), pp. 197-214], we solve the following problem. Given a digraph D = (V, A) and a matroid on a set S = {s(1), . . ., s(k)} along with a map pi : S -> V, find k edge-disjoint arborescences T-1, . . . , T-k with roots pi(s(1)), . . . , pi(s(k)), respectively, such that, for any v is an element of V, the set {s(i) : v is an element of T-i} is independent and its rank reaches the theoretical maximum. We also give a simplified proof for a result of [S. Fujishige, Combinatorica, 30 (2010), pp. 247-252].

引用

页码：2107 / 2114

页数：8

共 13 条

[1] BERCZI K., 2010, COMBINATORIAL OPTIMI, P1
[2] MATROID-BASED PACKING OF ARBORESCENCES
de Gevigney, Olivier Durand
Viet-Hang Nguyen
Szigeti, Zoltan
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) : 567 - 574
[3] Edmonds J., 1973, Combinatorial Algorithms, P91
[4] Frank A., 2011, Connections in Combinatorial Optimization
[5] FRANK A., 1981, C MATH SOC J BOLYAI, V25, P59
[6] A NOTE ON DISJOINT ARBORESCENCES
Fujishige, Satoru
[J]. COMBINATORICA, 2010, 30 (02) : 247 - 252
[7] ARC-DISJOINT IN-TREES IN DIRECTED GRAPHS
Kamiyama, Naoyuki
Katoh, Naoki
Takizawa, Atsushi
[J]. COMBINATORICA, 2009, 29 (02) : 197 - 214
[8] ROOTED-TREE DECOMPOSITIONS WITH MATROID CONSTRAINTS AND THE INFINITESIMAL RIGIDITY OF FRAMEWORKS WITH BOUNDARIES
Katoh, Naoki
Tanigawa, Shin-ichi
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) : 155 - 185
[9] A rooted-forest partition with uniform vertex demand
Katoh, Naoki
Tanigawa, Shin-ichi
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 24 (02) : 67 - 98
[10] Katoh N, 2009, LECT NOTES COMPUT SC, V5878, P524, DOI 10.1007/978-3-642-10631-6_54

← 1 2 →