Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

PACKING ARBORESCENCES IN RANDOM DIGRAPHS

Texto completo
Autor(es):
Hoppen, Carlos [1] ; Parente, Roberto F. [2] ; Sato, Cristiane M. [3]
Número total de Autores: 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
Número total de Afiliações: 3
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
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
Beneficiário:Jefferson Antonio Galves
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs