Function-Described Graphs (FDGs) have been introduced by the authors as a representation of an ensemble of Attributed Graphs (AGs) for structural pattern recognition alternative to first-order random graphs. In previous works, algorithms for the synthesis of FDGs and a branch-and-bound algorithm for error-tolerant graph matching, which computes a distance measure between AGs and FDG, have been reported. Since the worst-case complexity of that matching algorithm is exponential in the number of nodes, an approximate algorithm to compute a sub-optimal measure is proposed in this paper. Results in 3D-object recognition show that, although the computational time is reduced, there is only a slight decrease of effectiveness while classifying an AG against a set of FDGs.