PACKING ARBORESCENCES IN RANDOM DIGRAPHS

Author(s)

Hoppen, Carlos ^[1] ; Parente, Roberto F. ^[2] ; Sato, Cristiane M. ^[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

• 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