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