Re: maximum common subgraph
 From: GCRhoads <GCRhoads@xxxxxxxxxxxxxxx>
 Date: Mon, 01 Oct 2007 22:19:00 0700
On Sep 30, 4:02 pm, sor...@xxxxxxxxx wrote:
Dear all,
I quote fromhttp://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
* Input: Two graphs G1 and G2.
* Question: What is the largest subgraph of G1 isomorphic to a
subgraph of G2?
First, I'd like some clarifications. Do they mean _induced_ subgraph?
(http://en.wikipedia.org/wiki/Subgraph#Subgraphs) I suppose they mean
induced. Otherwise we could choose the subgraph G1' that contains min(
G1, G2) vertices and no edges and it would be the common subgraph
with the largest number of vertices.
Both subgraphs (the subgraph of G1 and the subgraph of G2) have to be
induced, or only the subgraph of G1?
You've misquoted the problem listed on the referenced page!
The page says,
"Question: What is the largest *induced* subgraph of G1 isomorphic to
a subgraph of G2."
subgraph of G2 does not have to be.From this I assume they mean the subgraph of G1 is induced but the
Second, they suggest the following algorithm:
One possible solution for this problem is to build a product graph, in
which the largest clique represents a solution for the MCS problem.
Please have a look at the talk pagehttp://en.wikipedia.org/wiki/Talk:Maximum_common_subgraph_isomorphism...
I've tried to apply their algorithm on the example in the figure, but
the algorithm does not produce the desired result. What did I
misunderstand?
The graph you drew is *NOT* the modular product graph, it is not even
close. E.g. you have A2 and B1 as the neighbors of A1 when in fact
the neighbors of A1 are B2, C3, C4, D3, and D4. The given definition
is misstated in a way that doesn't make sense. It should read, "Any
two vertices (u, v) and (u', v') ..." with the rest being the same.
Also, vertices u and u' must be distinct vertices in G1, and v and v'
are distinct in G2. If they are not distinct, then there is no edge
in the modular product graph. Does that clear up your confusion?
[It is easy to see that A1, B2, C3, and D4 do form a clique in the
modular product graph but it is not so easy to see that it is a
maximum clique.]
.
 Prev by Date: Re: Subset sum problem: probabilistic fast testing algorithm...
 Next by Date: Re: Exploiting limitations of Turing machines in Turing tests?
 Previous by thread: Re: Subset sum problem: probabilistic fast testing algorithm...
 Next by thread: Algorithm: Min cost in a 2D array
 Index(es):
Relevant Pages
