| Texto completo | |
| Autor(es): |
Dellamonica, Jr., Domingos
[1]
;
Kohayakawa, Yoshiharu
[2, 1]
;
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/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 |
| 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 |