Metric graph theory database search algorithms

Question

I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms 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.

Answer 1

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. 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. Bioinformatics 23(2), 232–239 (2007).

• Huahai He. (2007) Querying and mining graph databases. Ph.D. Dissertation. University of California at Santa Barbara, USA.