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.)

Arboricity and spanning-tree packing in random graphs

Texto completo
Autor(es):
Gao, Pu [1] ; Perez-Gimenez, Xavier [2] ; Sato, Cristiane M. [3]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Monash Univ, Melbourne, Vic - Australia
[2] Univ Nebraska, Lincoln, NE - USA
[3] Univ Fed ABC, Ctr Math Comp & Cognit, Santo Andre - Brazil
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 52, n. 3, p. 495-535, MAY 2018.
Citações Web of Science: 1
Resumo

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph g(n,p). For all p(n) is an element of {[}0,1], we show that, with high probability, T is precisely the minimum delta and {[}m/ (n - 1)], where delta is the minimum degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that the following holds. above this threshold, T equals floor {[}m/ (n - 1)] and A equals {[}m/ (n -1 )]. Below this threshold, T equals delta, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are randomly added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k -> infinity. (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