Efficient Graph Matching for Video Indexing

摘要

Traditionally graph algorithms have been of restricted use due to their exponential computational complexity in the general case. Recently a new class of graph algorithms for subgraph isomorphism detection has been proposed, one of these algorithms having quadratic time complexity. These new algorithms use a preprocessing step to allow rapid matching of an input graph against a database of model graphs. We present a new algorithm for largest common subgraph detection that provides a significant performance improvement over previous algorithms. This new algorithm is based on the work on preprocessed subgraph isomorphism detection by Messmer and Bunke [3].