SYSTOLIC ALGORITHMS AND VLSI IMPLEMENTATIONS FOR GRAPH-MATCHING PROBLEMS

With the advances of current microcircuit technologies, VLSI implementations reveal characteristics which are distinct from earlier digital systems. To fully utilize the tremendous computation power of a silicon surface, VLSI algorithms need to be carefully and systematically derived. Systolic algorithms and event-driven networks are the keys to future VLSI performance. Based on these distinct requirements, fundamental mathematical tools such as linear algebra, relational algebra, group theory, random variables and graph theory are applied toward the derivation and analysis of a representative problem, the graph-matching problems, and its implementation. Because of the systematic development based on mathematics, as opposed to human heuristics, the major computations of the derived algorithms are systematic matrix operations, and hence are easily mapped to asynchronous systolic implementations. An extended branch-and-bound formulation of the algorithm is also discussed. Finally, extentions to attributed-graph-matching and noisy-graph-matching are studied and a real world application is presented