Every Monotone Graph Property Is Testable
From MaRDI portal
Publication:3624375
DOI10.1137/050633445zbMath1229.05126OpenAlexW2076599430WikidataQ105584113 ScholiaQ105584113MaRDI QIDQ3624375
Publication date: 30 April 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/050633445
Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (16)
Testing graphs against an unknown distribution ⋮ Additive approximation for edge-deletion problems ⋮ Densities in large permutations and parameter testing ⋮ Additive stabilizers for unstable graphs ⋮ Hypergraph regularity and random sampling ⋮ Steady and ranging sets in graph persistence ⋮ The Bradley-Terry condition is \(L_1\)-testable ⋮ Hierarchy theorems for property testing ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Hierarchy Theorems for Property Testing ⋮ Testing permutation properties through subpermutations ⋮ Sublinear-time Algorithms ⋮ Hierarchy theorems for testing properties in size-oblivious query complexity ⋮ On the Query Complexity of Estimating the Distance to Hereditary Graph Properties ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Estimating parameters associated with monotone properties
This page was built for publication: Every Monotone Graph Property Is Testable
