Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery (Q1095944)

Graph embedding (subgraph isomorphism is an NP-complete problem of great theoretical and practical importance in the sciences, especially chemistry and computer science. This paper presents positive test results for techniques to speed embedding by modeling graphs with subroutines, precalculating edge tables, turning recursion into iteration, and using search-ordering heuristics. The expert system SYNCHEM2 searches for synthesis routes of organic molecules without the online guidance of a user, and this paper examines how embedding information helps to implement the central operations of SYNCHEM2: selection, application, and evaluation of chemical reactions. The paper also outlines the architecture of SYNCHEM2, analyzes the computational time complexity of embedding and related problems in graph isomorphism and canonical chemical naming, and suggests topics and techniques for further research.