Computer Science ›› 2012, Vol. 39 ›› Issue (12): 233-236.
Previous Articles Next Articles
Online:
Published:
Abstract: A property testing algorithm is required to highly probably distinguish the case that the input has predeter- mined property II and the case that the input is afar from having the property,for any given parameter s. If there is a property testing algorithm for II such that its query complexity is independent of the input size parameter n, II is called testable. Let H be a graph, H-free is the property of containing no copy of H. For any connected graph H, Uoldreich and Ron show that H-free is testable in bounded degree model. In adjacency matrix model, it proves that F}free is tester ble,for any given H.
Key words: Property testing, Query complexity, Regularity lemma, Regularity r}duction,hestability
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2012/V39/I12/233
Cited