[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Graph isomorphism / maximum common subgraph

From: Gábor Csárdi
Subject: Re: [igraph] Graph isomorphism / maximum common subgraph
Date: Mon, 2 May 2011 15:25:45 -0400

Hi Benjamin,

says that a possible way to find the maximum common subgraph is to
create the modular product of the two graphs, which does not seem to
be very difficult, and the then find the maximum clique in this graph,
for which igraph has algorithms. (The implementation in the 0.6
version is much faster.)

Even if your graphs have only 200 vertices, this might be a difficult
thing to calculate, because already the modular product will have
about 200x200 vertices, and you need to find the largest clique in
these, which is an NP-complete problem (of course).

I am not sure what you mean about "most accurate", you are interested
in approximate solutions?


On Mon, May 2, 2011 at 3:18 PM, Benjamin Wellmann <address@hidden> wrote:
> Hello igraph-help-list,
> I'm using python and I'm looking for a package that has algorithms to find the
>  'maximum common subgraph'/isomorphism 
> [http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem] 
> between two graphs.
> I would expect that the method 'get_subisomorphisms_vf2' would help me, but 
> is there a possibility to limit the search to the largest (maximum) 
> isomorphism with the highest number of nodes.
> Furthermore, my graphs are not 'very huge' (max. 200 nodes), do you have any 
> hints which algorithm could be the most accurate?
> Thanks for any help
> Benjamin
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help

Gabor Csardi <address@hidden>     MTA KFKI RMKI

reply via email to

[Prev in Thread] Current Thread [Next in Thread]