| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Fed Rio Grande do Sul, Matemat Pura & Aplicada, BR-91509900 Porto Alegre, RS - Brazil
[2] Univ Fed Bahia, Comp Sci, BR-40170120 Salvador, BA - Brazil
[3] Univ Fed ABC, CMCC, BR-49967950 Santo Andre, SP - Brazil
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 33, n. 1, p. 438-453, 2019. |
| Web of Science Citations: | 0 |
| Abstract | |
We study the problem of packing arborescences in the random digraph D(n, p), where each possible arc is included uniformly at random with probability p = p(n). Let lambda(D(n, p)) denote the largest integer lambda >= 0 such that, for all 0 <= l <= lambda we have Sigma(l-1)(i=0) (l-i)vertical bar[v : d(in) (v) = i]vertical bar <= l. We show that the maximum number of arc-disjoint arborescences in D (n, p) is lambda(D (n, p)) asymptotically almost surely. We also give tight estimates for lambda(D (n, p)) depending on the range of p. (AU) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat |
| Grantee: | Oswaldo Baffa Filho |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |