# Explain this Graph Matching solved in Linear Time

I'm interested in a better explanation about the paper Computing Optimal Assignments in Linear Time for Approximate Graph Matching.

The graph edit distance is approximated by assignments in linear time.

Briefly speaking there is an embedding of optimal assignment costs into a Manhattan metric: $$φ_c(A) = [A_{uv}^← · w(uv)]_{uv∈E(T)}$$. The Manhattan distance between these vectors is equal to the optimal assignment costs between the sets.

The problem is: it is not throughly explained how I find $$A_{uv}^←$$ and how I use Weisfeiler-Lehman to label the vertices of a tree in the following figure:

Please, explain how I find $$A_{uv}^←$$ and how I label that tree.