Rapid subgraph search using parallelism

A new parallel processing algorithm is reported for subgraph matching. Parallelism is achieved for the first time within the process of node-by-node matching of two individual graphs. A SIMULA program is described for simulating this parallel subgraph search algorithm. Simulation results from a series of chemical substructure search problems show an average utilization of 84% on a 25-processor machine and up to a 24-fold speed enhancement over a single processor. Potential applications include starting material selections for synthesis as well as general substructure search problems.