A PARALLEL ALGORITHM FOR GRAPH MATCHING AND ITS MASPAR IMPLEMENTATION

Search of discrete spaces is important in combinatorial optimization. Such problems arise in artificial intelligence, computer vision, opera tions research, and other areas. For realistic problems, the search sp aces to be processed are usually huge, necessitating long computation times, pruning heuristics, or massively parallel processing. We presen t an algorithm that reduces the computation time for graph matching by employing both branch-and-bound pruning of the search tree and massiv ely-parallel search of the as-yet-unpruned portions of the space. Most research on parallel search has assumed that a multiple-instruction-s tream/multiple-data-stream (MIMD) parallel computer is available. Sinc e massively parallel single-instruction-stream/multiple-data-stream (S IMD) computers are much less expensive than MIMD systems with equal nu mbers of processors, the question arises as to whether SIMD systems ca n efficiently handle state-space search problems. We demonstrate that the answer is yes, and in particular, that graph matching has a natura l acid efficient implementation on SIMD machines.