Testing versus Estimation of Graph Properties

DOI10.1137/060652324zbMath1247.05238OpenAlexW2007704435WikidataQ105584112 ScholiaQ105584112MaRDI QIDQ5386210

Eldar Fischer, Ilan Newman

Publication date: 22 April 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060652324

zbMATH Keywords

approximationgraph algorithmsproperty testingregularity Lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

On the benefits of adaptivity in property testing of dense graphs ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Estimating the distance to a hereditary graph property ⋮ Local-vs-global combinatorics ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Deterministic vs non-deterministic graph property testing ⋮ Unnamed Item ⋮ Parameter testing in bounded degree graphs of subexponential growth ⋮ Earthmover Resilience and Testing in Ordered Structures ⋮ Inflatable Graph Properties and Natural Property Tests ⋮ On the Query Complexity of Estimating the Distance to Hereditary Graph Properties ⋮ Estimating parameters associated with monotone properties

This page was built for publication: Testing versus Estimation of Graph Properties