Busca avançada
Ano de início
Entree
Conteúdo relacionado
(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.)

LOCAL ALGORITHMS, REGULAR GRAPHS OF LARGE GIRTH, AND RANDOM REGULAR GRAPHS

Texto completo
Autor(es):
Hoppen, Carlos [1] ; Wormald, Nicholas [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Fed Rio Grande do Sul, Inst Matemat & Estat, Porto Alegre, RS - Brazil
[2] Monash Univ, Sch Math Sci, Clayton, Vic - Australia
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: COMBINATORICA; v. 38, n. 3, p. 619-664, JUN 2018.
Citações Web of Science: 2
Resumo

We introduce a general class of algorithms and analyse their application to regular graphs of large girth. In particular, we can transfer several results proved for random regular graphs into (deterministic) results about all regular graphs with sufficiently large girth. This reverses the usual direction, which is from the deterministic setting to the random one. In particular, this approach enables, for the first time, the achievement of results equivalent to those obtained on random regular graphs by a powerful class of algorithms which contain prioritised actions. As a result, we obtain new upper or lower bounds on the size of maximum independent sets, minimum dominating sets, maximum k-independent sets, minimum k-dominating sets and maximum k-separated matchings in r-regular graphs with large girth. (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