I have two different graphs. These two share some sub-graphs. It is probably possible to find these regions with an exhaustive search, but it's not an option for me. I could not find the keywords for this problem. It's not sub-graph matching, since I have no query graph. I attached a sample situation. The inside of the red regions should be matched.
I would greatly appreciate any help.
Thank you for your very detailed answer. Really appreciate it. The first method can give me a really good representation of sub-graph. Btw, I forget to say that my graphs are attributed; therefore, this information can be used to select representative vertex.
I will try to implement and share the result here.
Thanks for keywords! Unfortunately, my sub-graphs are not complete(they can be, but not guaranteed), are they still suitable for my problem?
To avoid the extensive searching you need to adopt a systematic method to discover and classify sub graphs with searchable indexes.
I think it's called Maximum Common (Edge) Subgraph. There is a nice survey by Raymond and Willett, which is easily found by google.
https://en.wikipedia.org/wiki/Maximum_common_subgraph
Thank you! I think this is the keyword that I've been searching for.
Dear Cagatay Odabasi,
You are indeed looking for Maximum Common Subgraph Isomorphism algorithms, as Mathias Weller says. The most recent review (also by Professor Willett, as the one Mathias Weller mentioned) is in press in the journal "MATCH communications in mathematics and in computer chemistry":
E. Duesbury, J. D. Holliday, P. Willett: Maximum Common Subgraph Isomorphism Algorithms. Volume 77 (2017) number 2
See in the journal's page: http://match.pmf.kg.ac.rs/content77n2.htm
The full text is not available yet, you should write to Professor Willett and ask him for a copy ([email protected]).
Best regards,
Wilmer
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs