PACKING ARBORESCENCES IN RANDOM DIGRAPHS

Autor(es)

Hoppen, Carlos ^[1] ; Parente, Roberto F. ^[2] ; Sato, Cristiane M. ^[3]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 33, n. 1, p. 438-453, 2019.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
• Beneficiário: Oswaldo Baffa Filho
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs