Testing the diameter of graphs
Michal Parnas, Dana Ron · Random Structures and Algorithms · 2002
We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of [GR97]. In this model we present a family of algorithms that test whether the diameter of a graph is bounded by a given parameter D, or is ffl-far from any graph with diameter at most fi(D). The function fi(D) ranges between D+ 4 and 4D + 2, depending on the algorithm. All our algorithms run in time polynomial in 1=ffl.