On Efficient Distance Approximation for Graph Properties

Nimrod Fiat, Dana Ron

A distance-approximation algorithm for a graph property $\mathcal{P}$ in the adjacency-matrix model is given an approximation parameter $\epsilon \in (0,1)$ and query access to the adjacen…