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:

enter image description here

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.