Status: Bibliographieeintrag
Standort: ---
Exemplare:
---
| |  Online-Ressource |
|---|
| Verfasst von: | Hoppen, Carlos [VerfasserIn]  |
|---|
| | Kohayakawa, Yoshiharu [VerfasserIn] |
|---|
| | Lang, Richard [VerfasserIn] |
|---|
| | Lefmann, Hanno [VerfasserIn] |
|---|
| | Stagni, Henrique [VerfasserIn] |
|---|
| Titel: | On the query complexity of estimating the distance to hereditary graph properties |
|---|
| Verf.angabe: | Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni |
|---|
| E-Jahr: | 2021 |
|---|
| Jahr: | June 9, 2021 |
|---|
| Umfang: | 14 S. |
|---|
| Teil: | volume:35 |
|---|
| | year:2021 |
|---|
| | number:2 |
|---|
| | pages:1238-1251 |
|---|
| | extent:14 |
|---|
| Fussnoten: | Gesehen am 19.09.2021 |
|---|
| Titel Quelle: | Enthalten in: Society for Industrial and Applied MathematicsSIAM journal on discrete mathematics |
|---|
| Ort Quelle: | Philadelphia, Pa. : Soc., 1988 |
|---|
| Jahr Quelle: | 2021 |
|---|
| Band/Heft Quelle: | 35(2021), 2, Seite 1238-1251 |
|---|
| ISSN Quelle: | 1095-7146 |
|---|
| Abstract: | Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $\Gamma$ to being induced $\mathcal{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 $\mathcal{F}$. |
|---|
| DOI: | doi:10.1137/19M1283951 |
|---|
| URL: | Bitte beachten Sie: Dies ist ein Bibliographieeintrag. Ein Volltextzugriff für Mitglieder der Universität besteht hier nur, falls für die entsprechende Zeitschrift/den entsprechenden Sammelband ein Abonnement besteht oder es sich um einen OpenAccess-Titel handelt.
Volltext ; Verlag: https://doi.org/10.1137/19M1283951 |
|---|
| | Volltext: https://epubs.siam.org/doi/10.1137/19M1283951 |
|---|
| | DOI: https://doi.org/10.1137/19M1283951 |
|---|
| Datenträger: | Online-Ressource |
|---|
| Sprache: | eng |
|---|
| Sach-SW: | 05C35 |
|---|
| | 05C85 |
|---|
| | 05D40 |
|---|
| | 68W20 |
|---|
| | edit distance |
|---|
| | Frieze;Kannan regularity |
|---|
| | hereditary properties |
|---|
| | parameter testing |
|---|
| | removal lemma |
|---|
| K10plus-PPN: | 1770928952 |
|---|
| Verknüpfungen: | → Zeitschrift |
|---|
On the query complexity of estimating the distance to hereditary graph properties / Hoppen, Carlos [VerfasserIn]; June 9, 2021 (Online-Ressource)
68781168
