<p>This seems to be related to the <em>subgraph isomorphism problem</em> which is in general NP-complete, even without any weights. The corresponding Wikipedia article claims that it can be solved efficiently in certain cases, though.</p>
<p>If chemo- is anything like bioinformatics you will probably be interested in approximation algorithms in order to deal with noise, anyway. Also, given database lookup as application, there might be clever ideas for preprocessing that give you good amortised runtimes.</p>
<p>Found (not read) those:</p>
<ul>
<li><p>V. Lipets, N. Vanetik, E. Gudes. <a href="https://doi.org/10.1007/s10618-009-0132-7" rel="nofollow noreferrer">Subsea: an efficient heuristic algorithm for subgraph isomorphism.</a> Data Min. Knowl. Disc. 19, 320–350 (2009).</p>
</li>
<li><p>Yuanyuan Tian, Richard C. McEachin, Carlos Santos, David J. States, Jignesh M. Patel. <a href="https://doi.org/10.1093/bioinformatics/btl571" rel="nofollow noreferrer">SAGA: a subgraph matching tool for biological graphs.</a> Bioinformatics 23(2), 232–239 (2007).</p>
</li>
<li><p>Huahai He. (2007) <a href="https://dl.acm.org/doi/book/10.5555/1368898" rel="nofollow noreferrer">Querying and mining graph databases.</a> Ph.D. Dissertation. University of California at Santa Barbara, USA.</p>
</li>
</ul>


CC BY-SA 4.0
2010-09-29T12:12:09.710Z
2022-11-21T08:26:33.077Z
2022-11-21T08:26:33.077Z
Raphael
<p>I am (slowly) writing a review of the <a href="http://www.routledge.com/books/details/9781420082920/">Handbook of Chemoinformatics Algorithms</a> for SIGACT News.  One chapter discusses current software implementations, and the database searches (and other applications) don't seem to take advantage of as much information about the graphs as they could.  On the other hand, perhaps more theoretical algorithms would be too hard to implement.  It seems like a potential open area, though.</p>

<p>So here's my question:</p>

<p>Is there an overview (or a small handful of references) that discusses theory <em>and implementation</em> (hopefully) of algorithms of databases of graphs with metric information?  (Each edge is a distance, and each vertex has a volume.)  A chemistry-free description of an example problem would be: given a database of graphs, find all of them that contain a particular subgraph.</p>

CC BY-SA 2.5
2010-09-10T04:20:13.760Z
how important is it that the database has metric information ? there's tons of work on graph database searching, even in the bio realm, but I don't know about the volume/distance label issue
Suresh Venkat
CC BY-SA 2.5
2010-09-10T12:22:26.550Z
I'll know the answer to your question in a week or two.  The similarities to and differences with bioinformatics problems are not clear to me yet.
Aaron Sterling
<reference-request>
Metric graph theory database search algorithms
Aaron Sterling
# Metric graph theory database search algorithms

(Asked by: username_0 on 2010-09-09)

I am (slowly) writing a review of the [Handbook of Chemoinformatics Algorithms](http://www.routledge.com/books/details/9781420082920/) for SIGACT News. One chapter discusses current software implementations, and the database searches (and other applications) don't seem to take advantage of as much information about the graphs as they could. On the other hand, perhaps more theoretical algorithms would be too hard to implement. It seems like a potential open area, though.

So here's my question:

Is there an overview (or a small handful of references) that discusses theory *and implementation* (hopefully) of algorithms of databases of graphs with metric information? (Each edge is a distance, and each vertex has a volume.) A chemistry-free description of an example problem would be: given a database of graphs, find all of them that contain a particular subgraph.

**Tags:** reference-request

> **Comments:**
> **username_1**: how important is it that the database has metric information ? there's tons of work on graph database searching, even in the bio realm, but I don't know about the volume/distance label issue  
> **username_0**: I'll know the answer to your question in a week or two.  The similarities to and differences with bioinformatics problems are not clear to me yet.  

---

## 1 answers

### Answer by username_2 on 2010-09-29. Score: 2 | Accepted answer

This seems to be related to the *subgraph isomorphism problem* which is in general NP-complete, even without any weights. The corresponding Wikipedia article claims that it can be solved efficiently in certain cases, though.

If chemo- is anything like bioinformatics you will probably be interested in approximation algorithms in order to deal with noise, anyway. Also, given database lookup as application, there might be clever ideas for preprocessing that give you good amortised runtimes.

Found (not read) those:

* V. Lipets, N. Vanetik, E. Gudes. [Subsea: an efficient heuristic algorithm for subgraph isomorphism.](https://doi.org/10.1007/s10618-009-0132-7) Data Min. Knowl. Disc. 19, 320–350 (2009).
* Yuanyuan Tian, Richard C. McEachin, Carlos Santos, David J. States, Jignesh M. Patel. [SAGA: a subgraph matching tool for biological graphs.](https://doi.org/10.1093/bioinformatics/btl571) Bioinformatics 23(2), 232–239 (2007).
* Huahai He. (2007) [Querying and mining graph databases.](https://dl.acm.org/doi/book/10.5555/1368898) Ph.D. Dissertation. University of California at Santa Barbara, USA.


---

