Testing Euclidean minimum spanning trees in the plane
Artur Czumaj, Christian Sohler · ACM Transactions on Algorithms · 2008
Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is a Euclidean minimum spanning tree (EMST) of P or G differs from it in more than ϵ n edges. We assume that G is given in adjacency list representation and the point/vertex set P is given in an array. We present a property testing algorithm that accepts graph G if it is an EMST of P and that rejects with probability at least 2/3 if G differs from every EMST of P in more than ϵ, n edges. Our algorithm runs in O(√ n /ϵ ⋅ log 2 ( n /ϵ)) time and has a query complexity of O(√ n /ϵ ⋅ log ( n /ϵ)).