maximum common subgraph
- From: sorinm@xxxxxxxxx
- Date: Sun, 30 Sep 2007 20:02:33 -0000
Dear all,
I quote from http://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?
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 page
http://en.wikipedia.org/wiki/Talk:Maximum_common_subgraph_isomorphism_problem
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?
Thank you in advance,
Sorin
.
- Prev by Date: Re: Generalized Quine-McCluskey
- Next by Date: Subset sum problem: probabilistic fast testing algorithm...
- Previous by thread: Mathematical models for loop calculations
- Next by thread: Subset sum problem: probabilistic fast testing algorithm...
- Index(es):
Relevant Pages
|
