Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Hoppen, Carlos [1] ; Kohayakawa, Yoshiharu [2] ; Lang, Richard [3] ; Lefmann, Hanno [4] ; Stagni, Henrique [2]
Total Authors: 5
Affiliation:
[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
Total Affiliations: 4
Document type: Journal article
Source: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 35, n. 2, p. 1238-1251, 2021.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 17/02263-0 - Property testing and estimation of graph parameters
Grantee:Henrique Stagni
Support type: Scholarships abroad - Research Internship - Doctorate
FAPESP's process: 15/15986-4 - Asymptotic Combinatorics with Applications in Property Testing and Parameters Estimation.
Grantee:Henrique Stagni
Support type: Scholarships in Brazil - Doctorate
FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
Grantee:Guilherme Oliveira Mota
Support type: Research Grants - Young Investigators Grants