J'écris (lentement) une revue du Handbook of Chemoinformatics Algorithms pour SIGACT News. Un chapitre traite des implémentations logicielles actuelles, et les recherches dans la base de données (et d'autres applications) ne semblent pas tirer autant d'informations sur les graphiques que possible. D'un autre côté, il serait peut-être trop difficile de mettre en œuvre des algorithmes plus théoriques. Cela semble cependant être un espace ouvert potentiel.
Voici donc ma question:
Existe-t-il un aperçu (ou une petite poignée de références) qui discute de la théorie et de la mise en œuvre (espérons-le) d'algorithmes de bases de données de graphiques avec des informations métriques? (Chaque arête est une distance, et chaque sommet a un volume.) Une description exempte de chimie d'un exemple de problème serait: étant donné une base de données de graphiques, trouver tous ceux qui contiennent un sous-graphique particulier.
la source
Réponses:
Cela semble être lié au problème d'isomorphisme sous-graphique qui est en général NP-complet, même sans aucun poids. L'article Wikipédia correspondant affirme qu'il peut être résolu efficacement dans certains cas, cependant.
Si la chimio est quelque chose comme la bioinformatique, vous serez probablement intéressé par les algorithmes d'approximation afin de faire face au bruit, de toute façon. En outre, étant donné la recherche de base de données en tant qu'application, il peut y avoir des idées astucieuses pour le prétraitement qui vous donnent de bons temps d'exécution amortis.
Trouvé (pas lu) ceux-ci:
http://www.springerlink.com/content/4751121q3575v041/
http://bioinformatics.oxfordjournals.org/content/23/2/232.full
http://portal.acm.org/citation.cfm?id=1368898
Avertissement : Encore une fois, désolé pour la réponse de style commentaire; Je ne suis pas encore autorisé à commenter.
la source