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

An Improved Upper Bound on the Density of Universal Random Graphs

Texto completo
Autor(es):
Dellamonica, Jr., Domingos [1] ; Kohayakawa, Yoshiharu [1, 2] ; Roedl, Vojtech [1] ; Rucinski, Andrzej [1, 3]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 - USA
[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[3] Adam Mickiewicz Univ, Dept Discrete Math, PL-61614 Poznan - Poland
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 46, n. 2, p. 274-299, MAR 2015.
Citações Web of Science: 6
Resumo

We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G) of n-vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer d3 and a large enough constant C = C-d, as n, asymptotically almost all graphs with n vertices and at least Cn2-1/dlog1/dn edges contain as subgraphs all graphs with n vertices and maximum degree at most d. (c) 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014 (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