GRAPH EMBEDDING ALGORITHMS AND THEIR APPLICATIONS.

摘要

Graph embedding, also known as subgraph identification, is concerned with the ability to identify the existence of one graph in another. Backtracking algorithms for identifying subgraphs are presented with refinements to the dual depth first search. The algorithm has been modularized to avoid the unnecessary simultaneous searching used in the earlier algorithms. This modularization eliminated the redundancy of searching the pattern graph. Several versions of the pattern searching module were made incorporating various heuristics. Alternate search methods for the pattern were also examined. One alternative, using degree ordered depth first search, provided an improvement of 27% to 66% in execution time over the original method. Special hardware configurations were also examined for their ability to reduce real-time interaction.;Several applications of graph embedding were also examined and implemented. Using graph embedding for information retrieval allowed for a simpler query structure, eliminated normalization requirements, and avoided the need for predicate calculus. Another application was the use of embedding to partition a distributed database network's resources for concurrent use. Three problems concerning chemical applications are examined. They concerned themselves with determining subcompound existence for determining reactant availability. These applications would appear as part of a larger synthesizing system such as SYNCHEM.