3
$\begingroup$

Given two graphs with n vertices each, where apriori information regarding the similarity of each pair of vertices (between the source and target nodes) is given, is there a known concept for finding the (sub) optimal matching problem?

A "good" solution will match neighbor source vertices to neighbor targets (similarly to the QAP problem), but will also try to maximize the summed source-target similarity of the graph match solution.

$\endgroup$
5
  • 2
    $\begingroup$ If the similarity between two vertices is modelled with a weight on the edge between these two vertices, and the problem is solved as a maximum weight matching. Is it what you are looking for? $\endgroup$
    – fontanf
    Aug 15 at 12:21
  • $\begingroup$ Not quite, there are the edges representing each individual graph and the "theoretical" edges between the graphs, with the weights being the similarity metric. The problem is to find the bipartite matching (between the graphs, like the Hungarian algorithm), but with another constraint, that neighbor source nodes should be matched to neighbor target nodes. $\endgroup$
    – DsCpp
    Aug 15 at 18:34
  • $\begingroup$ So you have tWo sets of weights on each edge linking both graphs ? $\endgroup$
    – Kuifje
    Aug 15 at 20:15
  • $\begingroup$ So basically, you want to find a matching in which the source and target nodes are paired. Is that right? $\endgroup$ Aug 16 at 23:20
  • $\begingroup$ Correct, but the initial knowledge about source-target node similarity should be a constraint, and not only a "seed assumption" about the pairing. $\endgroup$
    – DsCpp
    Aug 17 at 5:52

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.