On Tuesday 09 March 2010 12:05:36 Leonid Chepelev wrote: > Glad to see someone concur. Though, Ullman may have seen the > subgraph isomorphism problem as finding the maximal common > subgraph. One could argue about this, but it's not really that > crucial.
Are you talking about "An Algorithm for Subgraph Isomorphism" (Ullmann, J. R., 1976, J. ACM, 23(1):31-42)? I don't think this algorithm solves MCS. Starting with an empty mapping from G1 to G2 and expanding it step by step does not necessarily produce all common subgraphs. Ullmann uses a fixed order of the vertices of G1 to "expand" the mapping. If there is no vertex of G2 the first vertex of G1 can be mapped to, the algorithm will terminate immediately. Nevertheless there may exist a common subgraph of size > 0. Nils ------------------------------------------------------------------------------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ Cdk-user mailing list Cdk-user@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/cdk-user
