Hi all, I'm trying to calculate the average edge weight within a certain neighbourhood for each vertex in a tree. Basically, I have a (minimum spanning) tree and I want to remove all edges whose weight is much larger than the weight of edges closeby. The result would be a forrest of several connected components (I'm working on a clustering algorithm). Currently I naively iterate over each edge. For each edge, I find the source and target vertex. Then, for both the source and the target vertices, I calculate the average weight in a certain neighbourhood using a recursive function as following simplified pseudocode indicates: E: List of edges in MST getNeighbourhoodStats( depth, startvertex, edge ){ out_edges = getIncedentEdges(startvertex) foreach out_edges as out if( out!=edge){ totweight += getWeight(out); if(depth>0) getNeighbourhoodStats(depth-1, target(out), out) } end } main(){ foreach E as e //Get the total weight on the left of the edge int totweight_left=0; getNeighbourhoodStats( 5, source( e), E, totweight_left ) //Get the total weight on the right of the edge int totweight_right=0; getNeighbourhoodStats( 5, target( e), E, totweight_right ) end } However, this approach is rather inefficient as a lot of calculations are redundant (takes about 10ms for 300 edges which is way too slow for the purpose I had in mind). Any ideas for a better solution? Tnx a lot, Kind regards, Vincent