Property testing in bounded degree graphs

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We further develop the study of testing graph properties asinitiated by Goldreich, Goldwasser and Ron. Whereas theyview graphs as represented by their adjacency matrix andmeasure distance between graphs as a fraction of all possiblevertex pairs, we view graphs as represented by boundedlengthincidence lists and measure distance between graphsas a fraction of the maximum possible number of edges.Thus, while the previous model is most appropriate for thestudy of dense graphs, our model is...