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

ON THE QUERY COMPLEXITY OF ESTIMATING THE DISTANCE TO HEREDITARY GRAPH PROPERTIES

Texto completo
Autor(es):
Hoppen, Carlos [1] ; Kohayakawa, Yoshiharu [2] ; Lang, Richard [3] ; Lefmann, Hanno [4] ; Stagni, Henrique [2]
Número total de Autores: 5
Afiliação do(s) autor(es):
[1] Univ Fed Rio Grande do Sul, Inst Matemat & Estat, Ave Bento Goncalves 9500, BR-91501970 Porto Alegre, RS - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil
[3] Heidelberg Univ, Inst Informat, Neuenheimer Feld 205, D-69120 Heidelberg - Germany
[4] Tech Univ Chemnitz, Fak Informat, Str Nationen 62, D-09111 Chemnitz - Germany
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 35, n. 2, p. 1238-1251, 2021.
Citações Web of Science: 0
Resumo

Given a family of graphs F, we prove that the normalized edit distance of any given graph Gamma to being induced F-free is estimable with a query complexity that depends only on the bounds of the Frieze-Kannan regularity lemma and on a removal lemma for F. (AU)

Processo FAPESP: 17/02263-0 - Teste de propriedades e estimação de parâmetros de grafos
Beneficiário:Henrique Stagni
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Processo FAPESP: 15/15986-4 - Combinatória Assintótica com Aplicações em Teste de Propriedades e Estimação de Parâmetros.
Beneficiário:Henrique Stagni
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
Beneficiário:Guilherme Oliveira Mota
Linha de fomento: Auxílio à Pesquisa - Jovens Pesquisadores