Graph matching algorithms and books

Recommended Posts

Hello,

I am start working with graph matching.

I need suggestions for good books and algorithms, in the topic graph matching, can someone help-me?

My problem can be statement as following:

There is two attributed graphs Gm=(Vm,Em) and Gd=(Vd,Ed) that should be merged. Each node vi in Vm contains 3 atributes, number of edges (in and out), area and color. Each node vi in Vd contains 3 atributes, number of edges (in and out), area and name. This should be formulated with an inexact graph matching problem with option for multiples nodes in Gm could be associated to one node in Vd.

I am trying to formulate the fitness functions, but i need examples to do this the right way. Can also you give-me a clue of the best algorithm to touch this problem?

Thanks,

Filipe

Share on other sites

• 4 weeks later...

Graph matching is a well known graph problem,

The problem can be solved by different methods ..

the optimal solution is known as the maximum matching,

Theory: Graph Matching

A good algorithm is Blossom Algorithm that utilize Augmentation\Orientation

Time Complexity of Blossom Algorithm: $O({V}^{2.376})$

Create an account

Register a new account